查找中间项算法PPT

习题1 38P37令S为一个n个正整数的集合 n为偶数 请设计一个有效算法 将S分为两子集S1和S2 使每个子集中有n 2个元素 而且S1中所有的元素和与S2中所有元素的和的差最大 这个算法的时间复杂性是什么 算法思路 对S集合中的数按非降序排序 排序后S的前1 n 2的元素为集合中较小的数 后n 2 1 n的元素为集合中较大的数 则前1 n 2元素的和与后n 2 1 n元素和的差最大 算法一 我们下面给出的算法采用选择排序算法进行数组排序 当完成整个数组一半排序时 就满足了后n 2 1 n的元素均大于前1 n 2的元素的元素 后n 2 1 n的元素就无需排序了 AlgorithmSP1Input AnarrayS 1 n ofnelements nisevenOutput S1 1 n 2 S2 1 n 2 1 fori 1ton 22 k i3 forj i 1ton FindtheIthsmallestelement 4 ifS j S k thenk j5 endfor6 ifk itheninterchangeS i andS k 7 endfor8 fori 1ton 2S1 i S i S2 i S i n 2 endfor 算法一 可看出算法执行元素的比较次数 第4句 为 1 2 n i n 1 2 3 2 2 3 2 1 2 4 3 2 1 交换次数界于0与n 2之间 时间复杂度 因此算法一的时间复杂度为 n2 算法一 第6句的元素赋值次数为0到3n 2第9 10句的元素赋值次数为n 算法一 算法中的排序部分可以选取不同的排序算法实现 下面给出不同排序算法的时间复杂度比较 思考 由于算法一中将前n 2每个元素排序实际上是不必要的 我们考虑应用第6章分治的SPLIT划分算法 首先 找出该集合中的中间值项 再应用SPLIT算法划分S集合为两部分 一部分小于等于中间值 另一部分大于中间值 这样就比全部排序节省了时间 算法二 寻找中间值或第k小元素算法 见书P109 寻找中项的一个直接方法就是对所有的元素排序并取出中间一个元素 这个方法需要 nlogn 的时间 因为任何基于比较的排序过程在最坏的情况下必须至少要花费这么多时间 见P211定理12 2 原来在一个具有n个元素的集合中 中项或通常意义的第k小元素 能够在最优的线性时间内找到 这个问题也称为选择问题 采用分治方法降低时间复杂度 基本思想 假设递归算法中 在每个递归调用划分步骤后 我们丢弃元素的一个固定部分 并且对余下的元素递归 则问题的规模以几何级数递减 将A分成3组A1 a amm A1 代表A1中元素的个数 A1 k returnselect A1 1 A1 k A1 A2 k returnmm A1 A2 k returnselect A3 1 A3 k A1 A2 算法二 假设A为n个元素集合 假设A 8 33 17 51 57 49 35 11 25 37 14 3 2 13 52 12 6 29 32 54 5 16 22 23 7 59 阙值 6 8 33 17 51 57 49 35 11 25 37 14 3 2 13 52 12 6 29 32 54 5 16 22 23 7 59 算法二 假设A 8 33 17 51 57 49 35 11 25 37 14 3 2 13 52 12 6 29 32 54 5 16 22 23 7 59 阙值 6 8 17 33 51 57 11 25 35 37 49 2 3 13 14 52 6 12 29 32 54 5 7 16 22 23 M 33 35 13 29 16 mm 29 算法二 将A分为三个子序列A1 8 17 11 25 14 3 2 13 12 6 5 16 22 23 7 15A2 29A3 33 51 57 49 35 37 52 32 54 59 10因为 A1 15 k 13所以第13小元素一定在A1中 设A A1重复上述过程 算法二 A 8 17 11 25 14 3 2 13 12 6 5 16 22 23 7 8 17 11 25 14 3 2 13 12 6 5 16 22 23 7 M 14 6 16 mm 14A1 8 11 3 2 13 12 6 5 7 A2 14 A3 17 25 16 22 23 A1 A2 10 k 13故第13小元素在A3中 算法二 算法二 算法6 4SELECT输入 n个元素的数组A 1 n 和整数k 1 k n 输出 A中的第k小元素Select A 1 n k 过程select A low high k P high low 1Ifpmm 7 Case A1 代表A1中元素的个数 A1 k returnselect A1 1 A1 k A1 A2 k returnmm A1 A2 k returnselect A3 1 A3 k A1 A2 8 Endcase 1 n n T n 5 n T 0 75n 算法二 快速排序的划分算法 mm 算法二 AlgorithmSP2Input AnarrayS 1 n ofnelements nisevenOutput S1 1 n 2 S2 1 n 2 mm select S 1 n n 2 n j 1 1 Whilei 1tonif S i mm thenj ifand j i thenS j 与S i 交换EndwhileO n 8 SPLIT S j n w 见P113 n 9 fori 1ton 2S1 i S i S2 i S i n 2 endfor n 因此 算法二的时间复杂度为 O n 柯侃1110379255李保森1110379256蒋志颀1110379254 mm 从左到右非降序排列的中值组集合 这里所有的元素都小于或等于中值集的中间值 这里所有的元素都大于或等于中值集的中间值 n 5 2 n 5 升序 A1 A3 A1 小于或等于mm的元素集 A3 大于或等于mm的元素集 A1 3 n 5 2 3 2 n 5 A3 3 n 5 2 3 2 n 5 A1 严格小于mm的元素集 A3 严格大于mm的元素集 A1 n A3 0 7n 1 2 A3 n A1 0 7n 1 2 算法二 估计算法的运行时间1 2步骤的算法运行时间是 1 步骤3为 n 由于每组排序的时间是一个常量 步骤4耗费 n 步骤5的所需的时间为T n 5 步骤6的所需时间为 n 步骤7的耗费时间最多为T 0 7n 1 2 现在我们希望通过底函数去掉常量1 2来表示这个比率 为此假设0 7n 1 2 0 75n 则0 7n 1 2 0 75n 1 即当n 44时 这个不等式将成立 这就是为什么这个算法中设置阈值为44的原因 对于n 44 算法所耗费的时间至多为T 0 75n 算法二 AlgorithmSP2Input AnarrayS 1 n ofnelements nisevenOutput S1 1 n 2 S2 1 n 2 mm select S 1 n n 2 n finded false 1 Whilei 1tonandnotfindedif S i mm thenfinded trueEndwhileO n interchangeS 1 andS i 1 在数组中找到第一个值为mm的元素与第一个元素交换 7 SPLIT S 1 n w 见P113 n 8 fori 1ton 2S1 i S i S2 i S i n 2 endfor n 因此 算法二的时间复杂度为 O n 算