第四章 分 治 算 法 §1. 算法基本思想 考虑下面折半搜索算法 程序4-1-1 折半搜索 template<class T> int BinarySearch(T a[], const T& x, int n) {// 在 数 组 a[0:n-1] 中 搜 索 x ， 数 组 中 的 元 素 满 足 a[0]<=a[1] //<= ···<=a[n-1]。如果找到x，则返回所在位置（数组元素的下标） ， //否则返回 –1 int left=0; int right=n-1; while(left<=right){ int middle=(left+right)/2; if(x==a[middle]) return middle; if(x>a[middle]) left=middle+1; else right=middle – 1; } return –1; //未找到x } while 的每次循环 （最后一次除外） 都将以减半的比例缩小搜索范围， 所以， 该循环在最坏的情况下需要执行 )(lognΘ 次。由于每次循环需耗时 )1(Θ ，因此在 最坏情况下，总的时间复杂性为 )(lognΘ 。 折半搜索算法贯彻一个思想，即分治 法。当人们要解决一个输入规模，比 如n，很大的问题时，往往会想到将该问题分解。比如将这n个输入分成k个不 同的子集。如果能得到k个不同的可独立求解的子问题，而且在求出这些子问题 的解之后，还可以找到适当的方法把它们的解合并成整个问题的解，那么复杂的 难以解决的问题就可以得到解决。 这种将整个问题分解成若干个小问题来处理的 方法称为分治法。一般来说，被分解出来的子问题应与原问题具有相同的类型， 这样便于采用递归算法。如果得到的子问题相对来说还较大，则再用分治法，直 到产生出不用再分解就可求解的子问题为止。 人们考虑和使用较多的是k=2的情 形，即将整个问题二分。以下用A[1:n]来表示n个输入，用DanC(p,q)表示处理 输入为A[p:q]情况的问题。 分治法控制流程 DanC(p,q) global n，A[1:n]; integer m,p,q; // 1≤p≤q≤n if Small(p,q) then return G(p,q); else m=Divide(p,q); // p≤m<q return Combine(DanC(p,m),DanC(m+1,q)); endif end DanC 这里，Small(p,q)是一个布尔值函数，用以判断输入规模为 q-p+1 的问题 是否小到无需进一步细分即可容易求解。若是，则调用能直接计算此规模下子问 题解的函数 G(p,q). 而 Divide(p,q )是分割函数，决定分割点， Combine(x,y) 是解的合成函数。如果假定所分成的两个问题的输入规模大致相等，则 DanC 总 的计算时间可用下面的递归关系来估计： ? ? ? + = 用时是 的用时算比较小时，直接求解运当输入规模 CombinenfnfnT nGng nT )()()2/(2 )(n)( )( （4.1.1） 例4.1.1 求n元数组中的最大和最小元素 最容易想到的算法是直接比较算法： 将数组的第 1 个元素分别赋给两个临时 变量：fmax=A[1]; fmin=A[1]; 然后从数组的第 2 个元素 A[2]开始直到第 n 个 元素逐个与 fmax 和 fmin 比较，在每次比较中，如果 A[i] > fmax，则用 A[i] 的值替换fmax的值；如果A[i] < fmin，则用A[i]的值替换fmin的值；否则保 持fmax（fmin）的值不变。这样在程序结束时的fmax、fmin的值就分别是数组 的最大值和最小值。这个算法在最坏情况下，元素的比较次数是 2(n-1)，而平 均比较次数为3(n-1)/2。 如果采用分治的思想，我们可以给出算法，其时间复杂性在最坏和平均用时 均为3n/2-2: 程序4-1-2 递归求最大最小值算法伪代码 MaxMin（i,j,fmax,fmin）//A[1:n]是n个元素的数组，参数i，j //是整数，1≤i≤j≤n，使用该过程将数组A[i:j]中的最大最小元 //分别赋给fmax和fmin。 global n, A[1:n]; integer i, j; if i=j then fmax=fmin=A[i]; \\子数组A[i:j]中只有一个元素 elseif i=j-1 then \\子数组A[i:j]中只有两个元素 if A[i]<A[j] then fmin=A[i]; fmax=A[j]； else fmin=A[j]; fmax=A[i]; endif else mid=?(i+j)/2?; \\子数组A[i:j]中的元素多于两个 MaxMin(i, mid, gmax, gmin); MaxMin(mid+1, j, hmax, hmin); fmax=max(gmax, hmax)； fmin=main(gmin, hmin)； endif end Maxmin 如果用 T(n)来表示 MaxMin 所用的元素比较数，则上述递归算法导出一个 递归关系式： ?? ?? ? ? ? ? ? >++ = = = 22)2/()2/( 21 10 )( nnTnT n n nT (4.1.2) 当n是2 的方幂时，设 k n 2= ，有 22/3 222 2)2(2 24)4/(4 2)2)4/(2(2 2)2/(2)( 1 11 1 ?= ?+= += ++= ++= += ? ?≤≤ ? ∑ n T nT nT nTnT kk ki ik L 无论是最好、最坏、还是平均情况，MaxMin 所用的比较数都是 3n/2-2，比前面 提到的算法(在最坏情况下)节省了 25％的时间。实际上，任何一种以元素比较 为基础的找最大最小元素的算法，其元素比较数的下界是 ? ? 22/3 ?n 。从这种意 义上来说，MaxMin 算法是最优的。然而，由于需要 ? ? 1log +n 级的递归，每次递 归调用需要将 i，j，fmax，fmin 和返回地址的值保留到栈中，所以需要多占用 了内存空间。而且由于这些值出入栈时也会带来时间开销，特别当A中元素的比 较次数和整 数i与j 的比较次数相差无几时， 递归求最大最小值算法未必比直接 求最大最小值算法效率高。 例4.1.2．搜索算法的时间下界 分析上节提到的折半搜索算法，我们已经知道其时间复杂度是 )(lognO 。 事实上，我们可以用一个二元比较树来分析折半搜索算法的时间复杂性。以下是 n=9的二元比较树： n＝9情况下折半搜索的二元比较树 由图可见，当 x 在数组 A 中时，算法在圆形顶点结束；不在 A 中时，算法 在方形顶点结束。因为 43 292 <≤ ，所以比较树的叶顶点都 在4或5 级上出现。 因而元素比较的最多次数为4。一般地有：当 [ ) kk n 2,2 1? ∈ 时，一次成功的折半搜 索至多做k次比较，而一次不成功的折半搜索或者做k-1次比较，或者做k次比 较。 现在假设数组A[1:n]满足：A[1]< A[2]< …< A[n]。要搜索元素x是否在 A中。 如果只允许进行元素间的比较而不允许对它们进行其它的运算，则所设计 94 5 7 61 3 8 2 的算法称为以比较为基础的算法 。 任何以比较为基础的搜索算法的执行过程都可 以用一棵二元比较树来描述。每次可能的比较用一个内顶点表示，对应于不成功 的结果有一个外顶点（叶顶点）与之对应。线性搜索和折半搜索的二元比较树如 下： 图4-1-1 模拟线性搜索过程 . . . . . . 图4-1-2 模拟折半搜索过程 定理 4.1.1 设数组 A[1:n]的元素满足 A[1]< A[2]< …< A[n]。则以比较为 基础， 判断 ]:1[ nAx∈ 的任何算法， 在最坏情况下所需的最少比较次数 Find(n) 不小于 ?log(n+1)?. 证明 通过考察模拟求解搜索问题的各种 可能算法的比较树可知， Find(n) 不大于树中由根到一个叶子的最长路径的距离。也就是说，在最坏情况下每种搜 索算法的比较次数都是比较树中由根到叶顶点的最长距离。在所有的树中，这个 x:A[1] x:A[2] x:A[n] 不成功 不成功 不成功 不成功 x:A[?(n+1)/2?] x:A[?(n+1)/2?] x:A[?(n+1)/2?-1] x:A[1] x:A[?(n+1)/2?] x:A[?(n+1)/2?+1] x:A[n] 不成功 不成功 不成功 不成功 不成功 不成功 不成功 不成功 最长距离以完全二叉树的最短。对于每个二叉比较树，必有n个内顶点 与x在A 中的n种可能的情况相对应。 如果一棵二叉树的所有内顶点所在的级数小于或等 于级数k，则最多有 12 ? k 个内顶点。因此 12 ?≤ k n ，即Find(n)=k ≥?log(n+1)?。 证毕 由定理可见，任何一种以比较为基础 的算法，其最坏情况下的所用时间不可 能低于 )(lognΘ 。因此，也就不可能存在其最坏情况下时间比折半搜索数量级 （阶）还低的算法。事实上，折半搜索所产生的比较树的所有外部顶点都在相邻 的两个级上，而且这样的二叉树使得由根到叶顶点的最长路径减至最小，因此， 折半搜索是解决搜索问题在最坏情况下的最优算法。 §2.关于排序算法 问题 ：已知n个元素的数组A[1:n]，将A中元素按不降顺序排列 。 null 归并排序算法 程序4-2-1 向有序数组插入元素 程序4-2-2 插入排序 template<class T> template<class T> void Insert(T a[], int& n, const T& x) void InsertionSort(T a[], int n) {//向数组a[0:n-1]中插入元素x {//对a[0:n-1]进行排序 //假定a的大小超过n for(int i=1; i<n; i++) { int i; T t =a[i]; for(i=n-1; i>=0 && x<a[i]; i--) Insert(a, i, t); a[i+1]=a[i]; } a[i+1]=x; } n++; //添加了一个元素 } 将上述两个算法合并在一起，得到下述插入排序算法： 程序4-2-3 插入排序算法伪代码 InsertSort (A,n) //将A[1:n]中的元素按非降次序排列，n ≥1 A[0]=?∞ //生成一个虚拟值 for j from 2 to n do // A[1:j-1]已经排序 item=A[j]; i=j?1; while item<A[i] do // 0≤i<j A[i+1]=A[i]; i=i?1; endwhile A[i+1]=item; endfor end InsertSort while循环中的语句可能执行j次（j=2,…,n）,因此最坏情况的时间限界是 )(1)2/)1(( 2 2 nnnj nj Θ=?+= ∑ ≤≤ 在这个算法中，大部分的时间都用在挪动元素上，随着已经排好顺序的数组 的增长，被挪动的元素的个数也在增加，而且在整个过程中，很多元素不止一次 被挪动。以下程序从某种程度上减少了这种浪费。这一算法的基本思想是采用， 分治的方法，将要排序的数组分成两部分，先对每部分进行排序，然后再将两部 分已经排好序的子数组的元素按照从小到大的顺序交替地摆放在一个新的数组 中。这一过程也许需要多次分解和组合，因而是一个递归过程。 程序4－2－4 归并排序主程序伪代码 MergeSort(low, high) // A[low : high]是一个全程数组，含有 // high-low+1个待排序的元素。 integer low, high; if low < high then mid = ?(low+high)/2? //求当前数组的分割点 MergeSort(low, mid) //将第一子数组排序 MergeSort(mid+1, high) //将第二子数组排序 Merge(low, mid, high) //归并两个已经排序的子数组 endif end MergeSort 这里我们使用了辅助程序Merge: 程序4-2-5 合并过程伪代码 Merge(low, mid, high) //已知全程数组A[low : high], 其由两部分已经排 \\好序的子数组构成：A[low : mid]和 A[mid+1 : high]。本程序的任务 \\是将这两部分子数组合并成一个整体排好序的数组， 再存于数组 \\A[low : high]. integer h, i, j, k, low, mid, high; global A[low : high]; local B[low : high]; //借用临时数组B h=low; i=low; j=mid+1; // h, j是拣取游标, i是存放游标 while h≤mid && j≤high do //当两个集合都没有取尽时 if A[h]≤A[j] then B[i]=A[h]; h=h+1; else B[i]=A[j]; j=j+1; endif i＝i+1; endwhile if h>mid then \\ 当第一子组元素被取尽，而第二组元素未被取尽时 for k from j to high do B[i]=A[k]; i=i+1; endfor else for k from h to mid do \\ 当第二子组元素被取尽，而第一组元素未被取尽时 B[i]=A[k]; i=i+1; endfor endif for k from low to high do \\将临时数组中元素再赋给数组A A[k]=B[k]; endfor end Merge 可见， 归并排序由分解与合并两部分组成， 整个过程可用两棵树表示出来 （参 见文档 “归并排序树” ） 。 如果用T(n)表示归并排序所用的时间， 并假定合并过程所用时间与n成正比： cn，其中c是一个正数，则有 ? ? ? >+ = = 1)2/(2 1 )( ncnnT na nT (4.2.1) 其中， a是一个常数。 若n是2 的方幂： k n 2= ，直接推导可得 ncnan kcnT cnnT cncnnTnT k log )1(2 2)4/(4 )2/)4/(2(2)( += += += ++= LL 对于一般的整数n，我们可以假定 1 22 + ≤< kk n ，于是 )2()( 1+ ≤ k TnT ，得 )log()( nnOnT = 。 null 以比较为基础的排序时间的下界 类似于估计搜索算法的时间下界，我们也可以用树来模拟排序算法，在此我 们考虑最坏情况下的时间下限，并假定数组中的元素互不相同。在树的内部顶点 上，算法执行一次比较，并根据比较的结果移向它的某一个孩子。由于每两个元 素A[i]和A[j]的比较只有两种可能：A[i]<A[j]或A[j]<A[i]，所以这颗树是二 叉树。当A[i]<A[j]时进入左分支，当A[j]<A[i]进入右分支。各个外部顶点（叶 顶点）表示算法终止。从根到外顶点的每一条路径与一种唯一的排列相对应。由 于 n 个不同元素的不同排列共有 n！个，因此比较树至多有 n！个外部顶点（参 看文档“ 排序比较树 ” ） 。直接观察可知，由根到外顶点路径即描述了该外顶点所 代表的排列生成过程，路径的长度即是经历的比较次数。因此，比较树中最长路 径的长度（其是比较树的高）即是算法在最坏情况下所做的比较次数。要求出所 有以比较为基础的排序算法在最坏情况的时间下界， 只需求出这些算法所对应的 比较树的最小高度。如果比较树的高是k，则该二叉树的外顶点至多是 k 2 个。于 是，最坏情况下的最少比较次数T(n)满足 )( 2! nT n ≤ 。注意到 ?? 12/ )2/()2/()1(! ? ≥?≥ n nnnnnL 因而 )log()2/log()12/()( nnnnnT Θ=?≥ 从上式看出，归并排序是时间复杂性级别最低的排序算法（以比较为基础） 。 然而，仔细观察可以发现，归并排序有两个地方值得商榷：一是分解直到只有一 个元素。事实上，当元素比较少时，直接进行排序，比如用插入排序算法，比起 进一步分拆、合并排序要快得多。因为，在这种情况下，大量的时间都花在调用 分解、合并函数上。所以，在归并排序算法中，对于 归并起点的规模 应该有适当 的限制，即加 Small(p,q)判断。二是辅助数组 B 的借用，虽然不可避免，但应 该采用另一种方式，以避免数组A中的元素的频繁换位。为此，我们可以采用链 表，将数组A中的元素位置变动转化成链表值的变化。 程序4-2-6 使用链接表的归并排序算法 MergeSortL(low, high, p) // Link是全程数组A[low:high]的 //下标表, p指示这个表的开始处。利用Lin k将A按非 //降顺序排列。 global A[low:high]; Link[low:high]; if high-low+1<16 then //设定子问题的最小规模Small InsertSort(A,Link, low,high,p)； else mid=?(low+high)/2?； MergeSortL(low,mid,q); //返回q表 MergeSortL(mid+1,high,r); //返回r表 MergeL(q,r,p); 将 表q和r 合并成表p endif end MergeSortL 其中，合并程序MergeL是合并函数Merge的改进： 程序4-2-7 使用连接表的合并程序 MergeL(q,r,p) // 由链接 表q和r 构造新的连接表p。q、r是全程数组 \\Link[1:n]中两个表指针，这两个链表指出被划分的两个子组的地址排 \\序， 而p指针指出两组归并后的地址排序。实际上都是表的相互顺序 \\在变。. global n,A[1：n], Link[0:n]; local integer i, j, k; i=q; j=r; k=0; // 初始化，新表在Link[0]处开始 while i≠0 && j≠0 do //当两个表皆非空时 if A[i]≤A[j] then Link[k]=i; k=i; i=Link[i]; //加一个新元素到此表 else Link[k]=j; k=j; j=Link[j]; endif endwhile if i=0 then Link[k]=j; else Link[k]=i; endif p=Link[0]; end MergeL 例 4.2.1 考虑将数组A=[50,10,25,30,15,70,35,55]按非降次序排列问题， 采用 改进的归并算法。这里主要说明链接表在合并函数 MergeL 被调用时的变化过程 （参看文档“ 归并链接表 ” ） 。 null 快速排序算法 另一个利用分治法思想的排序算法是 快速排序， 是由计算机科学家 C.A.R.Hoare 提出的。基本策略是：将数组 A[1:n]分解成两个子数组 B[1:p]和 B[p+1:n]，使得 B[1:p]中的元素均不大于 B[p+1:n]中的元素，然后分别对这里 两个数组中的元素进行排序（非降的） ，最后再把两个排好序的数组接起来即可。 一般的分解是从A中选定一个元素，然后将A中的所有元素同这个元素比较，小 于或等于这个元素的放在一个子组例，大于这个元素的放在另一个子组里。这个 过程叫做划分。 程序4-2-8 划分程序伪代码 Partition(m,p) // 被划分的数组是A[m,p-1]，选定做划分元素的是 //t=A[m]。 integer m, p, i; global A[m:p-1]; v=A[m]; i=m; loop loop i=i+1; until A[i]≥v repeat //自左向右查 loop p=p-1; until A[p]≤v repeat //自右向左查 if i<p then Swap(A[i],A[p]); //交换A[i]和A[p]的位置 else exit； endif repeat A[m]=A[p]; A[p]=v; // 划分元素在位置p end Partition 例4.2.2 划分程序时的执行情况： m=1, p=10的情形 原数组： 65 70 75 80 85 60 55 50 45 ＋∞ （演示过程） 在划分算法基础上，给出快速排序算法： 程序4-2-9 快速排序算法伪代码 QuickSort(p,q) //将数组A[1:n]中的元素A[p], A[p+1], … , //A[q]按不降次序排列，并假定A[n+1]是一个确定数， //且大于A[1:n]中所有的数。 integer p,q; global n, A[1:n]; if p<q then j=q+1; Partition(p,j); // 划分后j成为划分元素的位置 QuickSort(p,j-1); QuickSort(j+1,q); endif end QuickSort 由前面关于以比较为基础的排序算法的在最坏情况下的下界可知， 快速排 序算法在最坏情况下的时间复杂性应不低于 )log( nn? 。事实上，在快速算法中 元素比较的次数，在最坏情况下是 )( 2 nO 。这是因为，在Partition(m,p)的每一 次调用中，元素的比较次数至多是 p-m+1.把 QuickSort 过程按照划分来分层， 则第一层只调用Partition一次， 即Partition(1,n+1)， 涉及的元素为n个； 在 第二层调用Partition两次，所涉及到的元素是n-1个，因为在第一层被选定的 划分元素不在其中。若用N k 表示第k层调用Partition时所涉及的元素总个数， 则N k ≤n-k+1.这样在第k层调用Partition时发生的元素比较次数应不大于n-k. 注意到 1 ≤k≤n，因此 QuickSort 算法在 最坏情况下总的元素比较次数不超过 n(n-1)/2,即QuickSort最坏情况下的时间复杂性为 )( 2 nO 。 为了得到时间复杂性的平均值，我们不妨假设 1． 参加排序的n个元素互不相同； 2． Partition中的划分元素v是随机选取的。 以C A (n)记时间复杂性的平均值。在上述假设条件下，调用Partition(m,p)时， A[m, p-1]中各个元素成为划分元素的概率是相等的，因而留下待排序的两个子 组A[m: j-1]和A[j+1: p-1]的概率是1/(p-m).由此得递归关系式 ))()1(( 1 1)( 1 knCkC n nnC AA nk A ?+?++= ∑ ≤≤ (4.2.2) 其中， 1+n 是 Partition 第一次被调用时所需要的元素比较次数， 0)1()0( == AA CC 。将(4.3)式两端乘以n得 ))1()1()0((2)1()( ?+++++= nCCCnnnnC AAAA L (4.2.3) 用n-1替换(4.2.3)中的n得 ))2()1()0((2)1()1()1( ?++++?=?? nCCCnnnCn AAAA L (4.2.4) 再用(4.2.3)减去(4.2.4)式得 )1/(2/)1()1/()( ++?=+ nnnCnnC AA (4.2.5) 递归推导(4.2.5)式，并注意到 0)1()0( == AA CC ，得 ∑ +≤≤ +=+ 13 /122/)1()1/()( ni AA iCnnC (4.2.6) 利用积分不等式 )1ln(/1 1 2 13 +<≤ ∫ ∑ + +≤≤ n x dx i n ni 得 )log()1ln()1(2)( nnOnnnC A =++< 看来快速排序与归并排序具有相同的平均时间复杂性。 但是在实际表现中却 是有所不同的。教材中给出了一组实验数据。从这些数据看，快速排序一般要比 归并排序用时少些。 关于排序的算法我们已经接触了6种：计数排序、冒泡排序、插入排序、选 择排序、归并排序和快速排序，它们的时间复杂性列出如下： 算法 最坏复杂性 平均复杂性 冒泡排序 n 2 n 2 计数排序 n 2 n 2 插入排序 n 2 n 2 选择排序 n 2 n 2 快速排序 n 2 n log n 归并排序 n log n n log n 作业 ：1. 编写程序实现归并排序算法MergeSortL和快速排序算法QuickSort; 2. 用长分别为1000、2000、3000、4000、5000、6000、7000、8000、9000、 10000的10个数组的排列来统计这两种算法的时间复杂性； 3．提出你的改进算法设想。 §3.选 择 问 题 问题： 已知n元数组A[1:n]，试确定其中第k小的元素。 最容易想到的算法是采用一种排序算法先将数组按不降的次序排好， 然后从 排好序的数组中捡出第k小的元素。但这样的算法在最坏情况下至少是nlog n。 实际上，我们可以设计出在最坏情况下的 时间复杂度为 O(n)的算法。为此，考 擦上节提到的算法Partition。 假设在一次划分中， 划分元素v处于第j个位置。 如果 k<j，则要找的第 k 小元素在新数组 A[1:j-1]中，而且是 A[1:j-1]的第 k 小元素；如果k＝j，则划分元素v即是要找的第k小元素；如果k>j，则要找的 第k小元素在新数组A[j＋1:n]中,而且是A[j＋1:n]的第k-j小元素。 程序4-3-1 采用划分的选择算法 PartSelect（A, n, k）//在数组A[1:n]中找第k小元素t，并将其存 //放于位置k，即A[k]=t。而剩下的元素按着以t为划分元素的 //划分规则存放。再令A[n+1]=+∞. integer n, k, m, r, j; m=1; r=n+1; A[n+1]= +∞； loop j=r; Partition(m,j); // 返回的j是第j小元素的位置 case ：k=j : return : k<j : r=j; // j是新的下标上界 :else : m=j+1; //j+1是新的下标下界 endcase repeat end PartSelect （ 以划分程序的执行例子说明PartSelect程序的执行过程 ） 这个算法在最坏情况下的时间复杂度是 O(n 2 )。事实上，假定数组 A[1:n] 中的元素互不相同，而且假定 划分元素是随机选取 的。注意，在每次调用 Partition(m, j)都要耗去O(j-m+1)的时间。而下一次被划分的数组的元素个数 至少比上一次减少 1。因而，至多需要做 n 次划分。最初的划分中 m=1, j=n+1; 耗去时间至多为 n，第二次耗去时间至多是 n-1,… .所以，PartSelect 在最坏 情况下的时间复杂度为 O(n 2 )。但是，可以推出，PartSelect 的 平均复杂度为 O(n)。事实上，我们可以改进 PartSelect 算法，通过精心挑选划分元素 v，得 到在最坏情况下的时间复杂度为O(n)的算法。 程序4-3-2 改进的选择排序算法伪代码 Select(A, m, p, k) // 返回一个i值，使得A[i]是A[m:p]中第k小元 //素。r是一个大于1的整数。 global r; integer n, i, j; if p-m+1≤r then InsertSort(A, m, p); return(m+k-1); endif loop n=p-m+1; for i from 1 to ?n/r? do //计算中间值 InsertSort(A, m+(i-1)*r, m+i*r-1); //将中间值收集到A[m:p]的前部: Swap(A[m+i-1], A[m+(i-1)*r+?r/2?-1]); endfor j=Select(A, m, m+?n/r?-1, ??n/r?/2?); Swap(A[m], A[j]); //产生划分元素 j=p+1; Partition(m, j); case : j-m+1=k : return(j); : j-m+1>k : p=j-1; : else : k=k-(j-m+1); m=j+1; endcase repeat end Select 这里，程序Select只在划分元素的选取上做了改进，其余部分沿用PartSelect 的步骤。划分元素的选取方案是： 取定正整数 r(>1),将原始数组按 r 个元素一段的原则分成 ?n/r?段（可能剩 余n-r* ?n/r?个元素，但是算法中忽略它们的存在） 。对每一段求取中间元素，并 把这 ?n/r?个中间元素搜集在数组A[m:p]的前部（免去另开空间收存的操作） 。现 在调用程序 Select(A, m, m+ ?n/r?-1, ??n/r?/2?)，就产生了所要的划分元素。 因为 ?n/r?一定小于n， 这样的递归过程是可行的。 为了直接应用程序PartSelect， 将刚刚找到的划分元素放在数组 A[m: p]的首位。我们以 r=5 来分析 Select 算 法的时间复杂性。 假设数组A中的元素都是互不相同的。 由于每个具有5个元素的数组的中间 值u是该数组的第3小元素，此数组至少有3个元素不大于u； ?n/5?个中间值中 至少有 ??n/5?/2?个不大于这些中间值的中间值 v。因而，在数组 A 中至少有 3*??n/5?/2?=1.5*?n/5?元素不大于 v。换句话说，A 中至多有 n-1.5* ?n/5?≤ 0.7n+1.2 个元素大于 v。同理，至多有 0.7n+1.2 个元素小于 v。这样，以 v 为 划分元素所产生的新的数组至多有0.7n+1.2个元素。 当n ≥24时， 0.7n+1.2≤3n/4。 注意到程序 Select 中，从一层到下一层递归时，实际上相当于两次调用了 Select：一次体现在语句j=Select(A, m, m+ ?n/r?-1, ??n/r?/2?);另一次体现在 Partition(m, j);及后面 case 语句组。这两步涉及的数组规模分别是 n/5 和 ≤ 3n/4。程序中其它执行步的时间复杂性都至多是 n 的倍数。如果用 T(n)表示时 间复杂度，则当n ≥24时，有递归关系式 cnnTnTnT ++≤ )4/3()5/()( (4.3.1) 其中c是常数。用数学归纳法可以证明 cnnT 20)( ≤ (4.3.2) 所以，在最坏情况下，Select算法的时间复杂度是 )(nO 。 §4.关 于 矩 阵 乘 法 假定A, B都是n×n矩阵，它们的i行j 列元素分别记为A(i,j)和B(i,j)。 如果用S和C分别记A+B和 A*B, 则有 njijkBkiAjiC njijiBjiAjiS n k ≤≤= ≤≤+= ∑ = ,1),(*),(),( ,1),(),(),( 1 (4.4.1) 可见，矩阵加法运算的时间复杂度是 )( 2 nΘ ，而矩阵乘法的时间复杂度是 )( 3 nΘ 。 后者是因为求每个元素 ),( jiC 都需要n次乘法和n-1次加法运算， 而C共有 2 n 个 元素。 如果用分治法解决矩阵的乘法问题， 可以设想将矩阵分块，然后用分块矩阵 乘法完成原矩阵的乘法运算。不妨假 定n是2 的方幂， k n 2= ，将矩阵A和B等 分成四块，于是 ? ? ? ? ? ? = ? ? ? ? ? ? ? ? ? ? ? ? = 2221 1211 2221 1211 2221 1211 * CC CC BB BB AA AA BA 其中 22221221222122112121 22121211122112111111 BABACBABAC BABACBABAC +=+= +=+= (4.4.2) 如果用T(n)记两个n阶矩阵相乘所用的时间，则有如下递归关系式： ? ? ? >+ ≤ = 2)2/(8 2 )( 2 ndnnT nb nT (4.4.3) 这是因为在计算 C 的块 C ij 时，需要计 算 8 次 n/2 阶矩阵的乘法计算 和4次n/2 阶矩阵的加法计算，后者需要 2 dn 加法运算，这里d是一个常数。直接递推关系 式(4.4.3)得 3/)16(48/)( 23 ?+= ndbnnT 因为 0≠b ，所以 )()( 3 nnT Θ= 。 虽然没有降低时间复杂度，但给我们一个启示。 1969 年 ，斯特拉森 (V.Strassen)发现了降低矩阵乘法时间复杂度的可能性。注意到，计算矩阵的加 法比计算乘法的时间复杂度具有较低的阶 ):( 32 nn ，而在用分块矩阵乘法时，既 有矩阵加法又有矩阵乘法。如果能通过增加加法次数来减少乘法次数，则可能达 到降低矩阵乘法的时间复杂度的目的。为此他设计了一个算法用以计算(4.4.2) 式中的C ij ，共用了7次乘法和18次加(减)法。令 ))(( ))(( )( )( )( )( ))(( 22212212 12111121 221211 112122 221211 112221 22112211 BBAAV BBAAU BAAT BBAS BBAR BAAQ BBAAP +?= +?= += ?= ?= += ++= (4.4.4) 则 UQRPC SQC TRC VTSPC +?+= += += +?+= 22 21 12 11 (4.4.5) 由此得到的递推关系式为 ? ? ? >+ ≤ = 2)2/(7 2 )( 2 nannT nb nT (4.4.6) 直接推导可得 () () () () 81.2 27log 7log 4 7 log2 log log 2 1222 3 4 721 16 73 4 21 16 7 73 4 4 7 21 16 )2(7))4/7()4/7(4/71()( n n a n ba n b nan b an TannT n n kk Θ= ? ? ? ? ? ? ? += + ? ? ? ? ? ? ?= + ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? = +++++= ?? L (4.4.7) 从所得的结果看出，Strassen算法的时间复杂度依赖于2×2矩阵的乘法运算所 使用的乘法数。然而Hoperoft和Kerr在1971年已经证明：计算2×2矩阵的乘 积，7 次乘法是必要的。因而，降低矩阵乘法运算的时间复杂度应改用其它分块 的阶数，如采用3×3或5×5的块等。目前已知的最低的时间复杂度是 )( 36.2 nO 。 而目前所知道的矩阵乘法的最好下界仍是它的平凡下界 )( 2 n? 。因此，到目前为 止还无法确切知道矩阵乘法的时间复杂性。 Strassen 矩阵乘 法采用的技巧也可以用于计算大整数的乘积。参看《计算 机算法设计与分析》－王晓东编著，电子工业出版社，2001。