第二章 递归与分治策略.ppt

第二章递归与分治策略 本章学习的主要内容 第一节递归的概念第二节分治法的基本思想第三节二分搜索技术第四节大整数的乘法第五节快速排序第六节循环赛日程表第七节Strassen矩阵乘法 本章学习的主要内容 第八节合并排序第九节棋盘覆盖第十节线性时间选择 第一节递归的概念 分治法的设计思想是 将一个难以直接解决的大问题分割成一些规模较小的相同问题 以便分而治之 由分治法产生的子问题往往是原问题的较小模式 可以采用递归技术解决这些子问题 分治与递归经常同时应用在算法的设计上 2 1递归的概念 一个直接或间接地调用自身的算法称为递归算法 例2 1阶乘函数阶乘函数递归地定义为 计算阶乘的程序 intFactorial intn if n 0 return1 returnn Factorial n 1 例2 2Fibonacci数列 1 1 2 3 5 8 13 21 34 55 称为Fibonacci数列 计算Fibonacci的程序 intFibonacci intn if n 1 return1 returnFibonacci n 1 Fibonacci n 2 例2 3双递归函数 Ackerman函数 当一个函数及它的一个变量是由函数自身定义时 称这个函数是双递归函数 双递归函数 Ackerman函数A n m m 0和n 0 其定义如下 A n m m 0时 A 0 0 1A 1 0 2A n 0 n 2 n 2m 1时 A 0 1 1A 1 1 A A 0 1 0 A 1 0 2A 2 1 A A 2 1 1 0 A 2 0 2 2 4 2 2A 3 1 A A 3 1 1 0 A 4 0 4 2 6 2 3 A n 1 A A n 1 1 0 A n 1 1 2A n 1 1 A A n 2 1 0 2 A n 2 1 2 A 3 1 A 2 1 2叠加得A n 1 n 2 2 2 2 2n n 2 A n m m 2时 A 0 2 1A 1 2 A A 0 2 1 A 1 1 2当n 2A n 2 A A n 1 2 1 2A n 1 2 A n 1 2 A A n 2 2 1 2A n 2 2 A n 2 2 A A n 3 2 1 2A n 3 2 A n 3 2 A A n 4 2 1 2A n 4 2 A 1 2 A A 1 1 2 1 2相乘得 A n 2 2n 2的层数为n 包括所有的2 A n 4 增长速度非常快 以至于没有适当的数学式子表示 单变量的Ackerman函数 A n A n n n min k A k n 即 n 是使得A k n成立的最小的k值 A 0 A 0 0 1 1 0A 1 A 1 1 2 2 1A 2 A 2 2 4 3 4 2A 3 A 3 3 16 5 6 16 3 n 增长速度非常慢 2的层数为65536 包括所有的2 对于通常所见到的正整数有 n 4理论上 n 没有上界 随着n的增长 它以难以想象的慢速度趋向无穷大 例2 4排列问题 设R r1 r2 rn 是要进行排列的n个元素 Ri R ri 集合X中元素的全排列记为Perm X ri Perm X 表示在全排列Perm X 的每一个排列前加上前缀ri得到的排列 R的全排列递归定义如下 当n 1时 Perm R r1 r1是R中唯一的元素 当n 1时 Perm R 由 ri Perm Ri i 1 2 n 构成 templatevoidPerm Typelist intk intm if k m for inti 0 i m i cout list i cout endl else for inti k i m i Swap list k list i Perm list k 1 m Swap list k list i 完成list中下标索引从k到m的元素的排列 1 2 3 4 1 2 3 4 k 1 表示集合起始索引 m 4 表示集合终止索引 集合起始索引为k 1 2 m 4 表示集合终止索引 list Swap 1 1 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 k 1 表示集合起始索引 m 4 表示集合终止索引 集合起始索引为k 1 2 m 4 表示集合终止索引 Swap 1 1 list Swap 1 2 Swap 1 1 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 k 1 表示集合起始索引 m 4 表示集合终止索引 集合起始索引为k 1 2 m 4 表示集合终止索引 Swap 1 1 list Swap 1 2 Swap 1 1 1 2 3 4 2 3 1 4 Swap 1 2 Swap 1 3 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 k 1 表示集合起始索引 m 4 表示集合终止索引 集合起始索引为k 1 2 m 4 表示集合终止索引 Swap 1 1 list Swap 1 2 Swap 1 1 1 2 3 4 2 3 1 4 Swap 1 2 Swap 1 3 1 2 3 4 2 4 3 1 Swap 1 3 Swap 1 4 例2 5整数划分问题 将一个正整数n表示成一系列正整数之和n n1 n2 nk 其中n1 n2 nk 1 k 1 n1称为最大划分数 正整数n的一个这种表示称为正整数n的一个划分 正整数n的所有不同的划分的个数称为正整数n的划分数 记做p n 例2 5整数划分问题 P 6 116 n1 6最大划分数为65 1 n1 5最大划分数为54 2 4 1 1 n1 4最大划分数为43 3 3 2 1 3 1 1 1 n1 3最大划分数为32 2 2 2 2 1 1 2 1 1 1 1 n1 2最大划分数为21 1 1 1 1 1 n1 1最大划分数为1 例2 5整数划分问题 在正整数n的所有不同的划分中 将最大加数n1不大于m的划分个数记做q n m 即n1 m例如 q 6 6 11q 6 5 10q 6 4 9q 6 3 7 例2 5整数划分问题 P 6 11n 61 1 1 1 1 1 n1 1 q 6 1 12 2 2 2 2 1 1 2 1 1 1 1 n1 2 q 6 2 q 6 1 3 43 3 3 2 1 3 1 1 1 n1 3 q 6 3 q 6 2 3 4 3 74 2 4 1 1 n1 4q 6 4 q 6 3 2 7 2 95 1 n1 5q 6 5 q 6 4 1 9 1 106 n1 6q 6 6 q 6 5 1 10 1 11P 6 q 6 6 q 6 10 q 6 6 例2 5整数划分问题 q n 1 1 n 1n 1 1 1 1 n个1相加 n1 1q n m q n n m n n1 n m q n n 1 q n n 1 正整数n的划分由n1 n的划分和n1 n 1的划分组成q n m q n m 1 q n m m n m 1正整数n的最大加数n1 m的划分由n1 m和n1 m 1的划分组成 q 6 5 q 6 4 q 1 5 9 q 1 1 9 1 10q 6 4 q 6 3 q 2 4 7 q 2 2 7 1 q 2 1 7 1 1 9 例2 5整数划分问题 正整数n的划分数p n q n n 计算q n m 的递归函数如下 intq intn intm if n 1 m 1 return0 if n 1 m 1 return1 if n m returnq n n if n m returnq n m 1 1 returnq n m 1 q n m m 例2 6Hanoi塔问题 例2 6Hanoi塔问题 设A B C是三个塔座 开始时 在塔座A上有一叠共n个圆盘 这些圆盘自下而上 由小到大地叠在一起 各个圆盘从上到下编号为1 2 n 要求将塔座A上n个圆盘移到塔座B上 并仍然按同样顺序叠置 例2 6Hanoi塔问题 移动圆盘时应遵守规则 每次只移动一个圆盘任何时刻都不允许将较大的圆盘压在较小的圆盘之上在满足前2个规则的前提下 可将圆盘移至A B C中任一塔座上 例2 6Hanoi塔问题递归解决方案 当n 1时 将编号为1的圆盘从A移动到B 记为 1 A B 当n 1时利用B作为辅助塔座 将编号为1 n 1的圆盘从A移动到C 记为 n 1 A C usingB 将编号n的圆盘从A移动到B 记为 n A B 利用A作为辅助塔座 将编号为1 n 1的圆盘从C移动到B 记为 n 1 C B usingA 例2 6Hanoi塔问题 将n个盘子从A柱移到B柱上 借助于C柱voidHanoi intn intA intB intC if n 0 将n 1个盘子从A柱移到C柱上 借助于B柱Hanoi n 1 A C B 把第n个盘子从A柱移动到B柱Move n A B 将n 1个盘子从C柱移到B柱上 借助于A柱Hanoi n 1 C B A 返回 第二节分治法的基本思想 分治法的基本思想是将一个规模为n的问题分解为k个规模小的子问题 这些子问题互相独立且与原问题相同 递归地解这些子问题 然后将各个子问题的解合并得到原问题的解 分治法的一般算法设计模式 Divide and Conquer P if P n0 Adhoc P dividePintosmallersubinstancesP1 P2 Pk for i 1 i k i yi Divide and Conquer Pi returnMerge y1 y2 yk 分治法的设计模式中子算法的描述 P 是问题规模 Adhoc P 是基本子算法 用于直接解小规模问题 Merge y1 y2 yk 是合并子算法 用于将子问题P1 P2 Pk的解y1 y2 yk合并为P的解 分治法的分割原则 最好使子问题的规模大致相同 分治法的计算效率 前提 考虑将规模为n的问题分成k个规模为n m的子问题 无妨设n0 1 且Adhoc解规模为1的问题耗费1个单位时间 Merge耗费f n 个单位时间 T n 表示Divide and Conquer P 解规模为 P n的问题所需计算时间 则有 解递归方程T n T n kT n m f n kT n m k2T n m2 kf n m k2T n m2 k3T n m3 k2f n m2 kjT n mj kj 1T n mj 1 kjf n mj kwT n mw kw 1T n mw 1 kwf n mw 其中w 1 logmn 递归方程T n 的解 分析分治法时 通常的递归公式 我们关心的一般是最坏情况下的计算时间复杂度的上界 所以用 和用 是没有本质区别的 返回 第三节二分搜索技术 问题 给定已经由小到大排好序的n个元素a 0 n 1 现在要在这n个元素中找出一特定元素x 如果x在a中 则返回x在a 0 n 1 中的下标索引 否则返回 1 Na ve的解决方案 顺序搜索 将x与a中所有元素逐一进行比较 直至找到或搜索整个数组a 顺序搜索方法需要O n 次比较 二分搜索算法的基本思想 将n个元素分成个数大致相同的两半 取a n 2 与x作比较若x a n 2 则找到x 算法终止 若xa n 2 则在数组的右半部继续搜索x 二分搜索算法 templateintBinarySearch Typea constType 二分搜索算法的效率分析 二分搜索算法经过每次和中间元素比较 相当于问题的规模由原来的n变成n 2 从分治法的角度 二分搜索算法相当于把原来规模为n的问题分解成1个子问题 子问题的规模为n 2 即分治法的递归方程中k 1 m 2将k k 1 个子问题合并为原问题的解需要用O 1 个单位时间 二分搜索算法的效率分析 因此二分搜索算法的计算效率 k 1 m 2 返回 第四节大整数的乘法 问题 计算两个n位二进制整数X和Y的乘法 n很大 以至于无法在计算机硬件能直接表示的整数范围内进行处理 可以把X和Y想象成很长的0和1序列 两个一位数的乘法称为位乘法 两个一位数的加法称为位加法 Na ve的解决方案 用小学所学的计算乘积的方法设计XY乘积的算法 X的每一位都要和Y中所有01进行乘积 要进行O n2 次位乘法 然后再进行n个二进制整数的相加 用分治法解决大整数乘法 将n位的二进制整数X和Y都分成2段 每段的长为n 2位 X Y X A 2n 2 B Y C 2n 2 DXY A 2n 2 B C 2n 2 D AC2n AD BC 2n 2 BD 用分治法解决大整数乘法 按前式 需要进行4次n 2位整数的乘法 即计算AC AD BC和BD需要3次不超过2n位的整数加法 还需要2次移位 一次是移动n位 对应于乘2n 一次是移动n 2位 对应于乘2n 2 所有加法和移位共用O n 步运算 分治法解决大整数乘法的效率 设T n 是2个n位整数相乘所需的运算总数 则有 k 4 m 2 改进 XY A 2n 2 B C 2n 2 D AC2n AD BC 2n 2 BD AC 2n A B D C AC BD 2n 2 BD需要作3次乘法 即AC BD A B D C 6次加法 2次移位 即k 3 m 2 k 3 m 2 返回 第五节快速排序 快速排序算法是基于分治策略的一个排序算法 快速排序的基本思想 输入的子数组a p r 按以下三个步骤进行 1 分解 Divide 以a p 为基准元素将a p r 划分成3段 小于a p 的部分 a p 大于a p 的部分 a p q 1 a q a q 1 r 2 递归求解 Conquer 通过递归调用快速算法分别对a p q 1 和a q 1 r 进行排序 3 合并 Merge 由于对a p q 1 和a q 1 r 的排序是就地进行的 所以在a p q 1 和a q 1 r 都已排好的序后不需要执行任何计算a p r 就已排好序 快速排序算法 templatevoidQuickSort Typea intp intr if p r intq Partition a p r QuickSort a p q 1 对左半段排序QuickSort a q 1 r 对右半段排序 对含有n个元素的数组a 0 n 1 进行快速排序只要调用QuickSort a 0 n 1 即可 上述算法中的函数Partition 以一个确定的基准元素a p 对子数组a p r 进行划分 它是快速排序算法的关键 templateintPartition Typea intp intr inti p j r 1 Typex a p 将 x的元素交换到左边区域 将x if i j break Swap a i a j a p a j a j x rerurnj 3 9 1 6 5 4 8 2 10 7 i j 3 3 9 1 6 5 4 8 2 10 7 i j 2 9 1 6 5 4 8 3 10 7 i j 2 9 1 6 5 4 8 3 10 7 i j 2 3 1 6 5 4 8 9 10 7 i j 2 3 1 6 5 4 8 9 10 7 j 2 1 3 6 5 4 8 9 10 7 i 3 9 1 6 5 4 8 2 10 7 i j 3 3 9 1 6 5 4 8 2 10 7 j j i j i j j i i 3 2 1 6 5 4 8 9 10 7 i 3 2 1 6 5 4 8 9 10 7 3 2 1 6 5 4 8 9 10 7 3 2 1 6 5 4 8 9 10 7 1 2 3 6 5 4 8 9 10 7 对于输入序列a p r Partition的计算时间显然为O r p 1 快速排序的运行时间与划分是否对称相关 最坏情况发生在划分过程产生的两个区域分别包含n 1个元素和1个元素的时候 最好的情况下 每次划分所取的基准都恰好为中值 即每次划分都产生两个大小为n 2的区域 最坏情况的划分 由于函数Partition的计算时间为O n 所以如果算法Partition的每一步都出现这种不对称划分 则其计算时间复杂性T n 满足 T n T n 1 nT n 1 T n 2 n 1T n 2 T n 3 n 2 T 2 T 1 2T n n n 1 n 2 2 1 O n2 最好情况的划分 由于函数Partition的计算时间为O n 所以如果算法Partition的每一步都出现对称划分 则其计算时间复杂性T n 满足 k 2 m 2 随机选择策略的快速排序算法 快速排序算法的性能取决于划分的对称性 在快速排序算法的每一步中 当数组还没有被划分时 可以在a p r 中随机选出一个元素作为划分基准 这样可以使划分基准的选择是随机的 从而可以期望划分是较对称的 随机化的划分算法 templateintRandomizedPartition Typea intp int r inti Random p r Swap a i a p ReturnPartition a p r 随机化的快速排序算法 随机化的快速排序算法通过调用RandomizedPartition来产生随机划分 templateviodRandomizedQuickSort Typea intp int r if p r intq RandomizedPartition a p r RandomizedQuickSort a p q 1 对左半段排序RandomizedQuickSort a q 1 r 对右半段排序 舍伍德洗牌算法 templatevoidShuffle Typea intn 随机洗牌算法RandomNumbermd for inti 1 i n i intj md Random n i 1 i Swap a i a j 返回 第六节循环赛日程表 问题的提出 设有n 2k个运动员要进网球循环赛 现要设计一个满足以下要求的比赛日程表 1 每个选手必须与其他n 1个选手各赛一次 2 每个选手一天只能赛一次 3 循环赛一共进行n 1天 用分治法来分析该问题 我们可按要求将比赛日程表设计成有n行和n 1列的一个表 在表中第i行和第j列出填入第i个选手在第j天所遇到的选手 按分治策略 我们可以将所有选手分为2组 n个选手的比赛日程表就可以通过为n 2个选手设计的比赛日程表来决定 递归地用这种一分为2的策略对选手进行分割 直到只剩下2个选手时 比赛日程表的制定就变得很简单 8 23 名选手的比赛日程表 算法的分治思想 其中左上角与左下角的2个小块分别为选手1至选手4和选手5至选手8前3天的比赛日程表 将左上角小块中的所有数字按其相对位置抄到右下角 将左下角小块中的所有数字按其相对位置抄到右上角 这样我们就分别安排好了选手1至选手和选手5至选手8在后4天的比赛日程 依此思想容易将这个比赛推广到具有任意多个选手的情形 算法的一般形式描述如下 voidTable ingk int a intn 1 for inti 1 i k i n 2 for inti 1 i n i a 1 i i intm 1 for ints 1 s k s n 2 for intt 1 t n t for inti m 1 i 2 m i for intj m 1 j 2 m j a i j t 1 m 2 a i m j t 1 m 2 m a i j t 1 m 2 m a i m j t 1 m 2 m 2 返回 第七节Strassen矩阵乘法 问题 设A aij n n和B bij n n是2个n乘n的矩阵 它们的乘积C AB cij n nNa ve的解决方案 按定义计算 每计算一个cij需要做n次乘法和n 1次加法 要计算C中的n2个元素所需时间为O n3 Strassen矩阵乘法 分治策略 假设矩阵的阶n是2的幂 将矩阵A B和C中每一矩阵都分块成为4个大小相等的子矩阵 每个自矩阵的阶都是n 2 Strassen矩阵乘法 分治策略 C11 A11B11 A12B21C12 A11B12 A12B22C21 A21B11 A22B21C22 A21B12 A22B22矩阵乘法的递归定义 n 2 需要8次乘法和4次加法n 2 继续将矩阵分成4块 Strassen矩阵乘法 分治策略 令T n 为分治法计算时间 则 k 8 m 2 改进 M1 A11 B12 B22 M2 A11 A12 B22M3 A21 A22 B11M4 A22 B21 B11 M5 A11 A22 B11 B22 M6 A12 A22 B21 B22 M7 A11 A21 B11 B12 C11 M5 M4 M2 M6C12 M1 M2C21 M3 M4C22 M5 M1 M3 M7 Strassen矩阵乘法效率分析 需要进行7次n 2阶矩阵乘积和18次n 2阶矩阵加减运算 k 7 m 2 Strassen矩阵乘法的未来研究 矩阵乘法的研究仍然在继续 Hopcroft和Kerr已经于1971年证明 计算2个2乘2阶矩阵乘法需要7次乘法 这说明要想进一步改进矩阵乘法的性能 不能再基于2乘2阶矩阵乘法 在Strassen之后有许多改进算法 在中键入关键字 Strassenmatrix 可搜索到较新的前沿研究成果 第八节合并排序 合并排序算法是用分治策略实现对n个元素进行排序的算法 基本思想 当n 1时 终止排序 当n 1时 将待排序元素分成大小大致相同的两个子集合 分别对两个子集合进行排序 最终将排好序的子集合合并为所要求的排好序的集合 合并排序算法的描述 templatevoidMergeSort Typea intleft intright Type b newType n if left right inti left right 2 MergeSort a left i MergeSort a i 1 right Merge a b left i right Copy a b left right 最坏情况的时间复杂度 由于函数Merge和Copy的计算时间为O n 算法MergeSort的每一步都出现对称划分 则其计算时间复杂性T n 满足 k 2 m 2 49386597 7613274938 6597 7613 2749 38 65 97 76 13 27 49 38 65 97 76 13 27 3849 6597 1376 27 38496597 132776 13273849657697 合并排序例子 自然合并排序 自然合并排序是MergeSort的一个变形 对于初始给定的数组a 通常存在多个长度大于1的已经自然排好序的子数组段 用1次对数组a的线性扫描 就足以找出所有这些排好序的子数组段 然后将相邻的排好序的子数组两两合并 构成更大的排好序的子数组段 4938659776132749 386597 76 1327 49 386597 76 1327 38496597 132776 13273849657697 自然合并排序例子 返回 第九节棋盘覆盖 相关概念 在一个2k 2k个方格组成的棋盘中 若恰有一个方格与其它的不同 则称该方格为一特殊方格 且称该棋盘为一特殊棋盘 特殊方格在棋盘上出现的位置有4k种情况 因而对任何k 0 有4k种不同的特殊棋盘 棋盘覆盖问题 我们要用下图所示的4种不同的L型骨牌覆盖一个给定的特殊棋盘上除特殊方格以外的所有方格 且任何2个L型骨牌不得重叠覆盖 易知 在任何一个2k 2k的棋盘覆盖中 用到的L型骨牌个数恰为 4k 1 3 a b c d 分治策略当k 0时 我们将2k 2k棋盘分割成4个2k 1 2k 1的子棋盘 特殊方格必位于4个子棋盘之一 其余的棋盘没有特殊方格 为了把这3个普通的方格转化成特殊的棋盘 可以用一个L型骨牌覆盖这3个子棋盘 连续用这种方法直到把棋盘简化成2 2的棋盘 棋盘覆盖的时间复杂度 设T k 是算法ChessBoard覆盖一个2k 2k棋盘所需的时间 则其计算时间复杂性T k 满足 解此递归方程可得T k O 4k 由于覆盖一个2k 2k棋盘所需的L型骨牌个数为 4k 1 3 故算法ChessBoard是一个在渐近意义下的最优的算法 第十节线性时间选择 线性时间选择问题的提法 元素选择问题的一般提法是 给定线性序集中n个不同的元素和一个整数k 1 k n要求找出这n个元素中第k小的元素 即如果将这n个元素依其线性序排列时 排在第k个位置的元素即为我们要找的元素 当k 1时 就是要找最小的元素 当k n时 就是要找最大的元素 当k n 1 2 时 称为找中位数 找n个元素的最小元素和最大元素可以在O n 时间完成 如果k log n n即k n log n 通过堆排序算法可以在O n k log n O n 时间内找出第k小元素 先建小头堆 时间耗费O n 再取k次堆顶元素 时间耗费O k log n 总时间耗费O n k log n O n 分治算法RandomizedSelect a p r k p r p r RandomizedPartition a p r i 小于等于a i 的元素个数j i p 1 大于a i 的元素个数r i a k j RandomizedSelect a p i k 分治算法RandomizedSelect a p r k p r p r RandomizedPartition a p r i 小于等于a i 的元素个数j i p 1 大于a i 的元素个数r i a k j RandomizedSelect a i 1 r k j 3 9 1 6 5 4 8 2 10 7 i j 3 3 9 1 6 5 4 8 2 10 7 j j i j i j j i i 3 2 1 6 5 4 8 9 10 7 i 3 2 1 6 5 4 8 9 10 7 3 2 1 6 5 4 8 9 10 7 3 2 1 6 5 4 8 9 10 7 1 2 3 6 5 4 8 9 10 7 如果要找第6小的元素 只需在 6 5 4 8 9 10 7 找第3小的元素 如果要找第2小的元素 只需继续在 1 2 3 找第2小的元素 一般选择问题的一个分治算法RandomizedSelect templateTypeRandomizedSelect Typea intp intr intk if p r returna p inti RandomizedPartition a p r j i p 1 if k j returnRandomizedSelect a p i k elsereturnRandomizedSelect a i 1 r k j 找数组a 0 n 1 第k小元素调用RandomizedSelect a 0 n 1 k 算法RandomizdSelect中执行RandomizedPartiton后 数组a p r 划分成两个子数组a p i 和a i 1 r 使得a p i 中每个元素都不大于a i 1 r 中每个元素 接着算法计算子数组a p i 中元素个数j 如果k j 则a p i 中第k小元素落在子数组a p i 中如果k j 则要找的第k小元素落在子数组a i 1 r 中 由于此时已知道子数组a p i 中元素均小于要找的第k小的元素 因此 要找的a p r 中第k小的元素是a i 1 r 中的第k j小的元素 在最坏情况下 算法RandomizedSelect需要 n 计算时间 例如在找最小元素时 总是在最大元素处划分 n 1 n 2 1 n 算法RandomizedSelect不稳定的原因是由于随机划分函数RandomizedPartition使用了一个随机数产生器Random 它能随机地产生p和r之间的一个随机整数 因此 RandomizedPartition产生的划分基准是随机的 可以证明 算法RandomizedSelect可以在O n 平均时间内找出n个输入元素中的第k小元素 解决算法RandomizedSelect不稳定 方法 寻找一个好的划分基准 使得按这个基准所划分出来的两个子数组的长度至少有一个为原数组长度的 倍 0 1是某个正常数 那么在最坏情况下用O n 时间就可以完成选择任务 例如 若 9 10 算法递归调用所产生的子数组的长度至少缩短1 10 在最坏情况下 算法所需的计算时间T n 满足递归式 T n T 9n 10 O n 由此可得 T n O n 寻找一个好的划分基准步骤 1 将n个输入元素划分成n 5个组 每组5个元素 除可能有一组不是5个元素外 用任意一种排序算法 将每组中的元素排好序 并取出每组的中位数 共n 5个 2 递归调用Select来找出这n 5个元素的中位数 如果n 5是偶数 就找它的两个中位数中较大的一个 然后以这个元素作为划分基准 其中n个元素用小圆点来表示 绿色小圆点为每组元素的中位数 中位数的中位数x为红色小圆点 图中所画箭头是由较大元素指向较小元素 x 5 6 4 3 7 9 10 1 12 11 13 15 2 8 14 5 6 4 3 7 中位数为5 9 10 1 12 11 中位数为10 13 15 2 8 14 中位数为135 10 13的中位数为10所选的基准元素为10 5 6 4 3 7 9 10 1 12 11 13 15 2 8 1410 6 4 3 7 9 5 1 12 11 13 15 2 8 1410 6 4 3 7 9 5 1 12 11 13 15 2 8 1410 6 4 3 7 9 5 1 8 11 13 15 2 12 1410 6 4 3 7 9 5 1 8 2 13 15 11 12 142 6 4 3 7 9 5 1 8 10 13 15 11 12 14 i j i j i j i j 10 15 2 3 1 1 3 为了简化问题 我们先设所用元素互不相同 找出的基准x至少比3 n 5 10个元素大 在每一组中有两个元素小于本组的中位数 n 5个中位数中有 n 5 1 2 n 5 10个小于基准x 比基准x小的元素个数至少为3 n 5 10 找出的基准x至少比3 n 5 10个元素小 在每一组中有两个元素大于本组的中位数 n 5个中位数中有 n 5 1 2 n 5 10个大于基准x 比基准x大的元素个数至少为3 n 5 10 而当n 75时 3 n 5 10 n 4 所以按此基准划分所得的两个子数组的长度都至少缩短1 4 TemplateTypeSelect Typea intp intr intk if r p 75 用某个简单排序算法对数组a p r 排序 returna p k 1 for inti 0 i r p 4 5 i 将a p 5 i 至a p 5 i 4 的第3小元素与a p i 交换位置 中位数的中位数放在a p p r p 4 5 找中位数的中位数 r p 4即上面所说的n 5Typex Select a p p r p 4 5 r p 4 10 inti Partition