算法设计与分析(三)分治法.ppt
123页
算法设计与分析算法设计与分析2011.92011.9(ACM(ACM创新实验班创新实验班) ) ——“分而治之”的问题求解策略3.1 3.1 一般方法一般方法1. 1. 问题的提出问题的提出 用计算机进行问题求解时，如果问题的规模n很小，可以直接求解，如排序问题，当n=1时，不需任何计算即可完成 当n=2时，作一次比较即可当n=3时，作3次比较也可完成，…当n比较大时，问题求解就不那么容易了一般情况下，要想直接解决一个规模较大的问题，有时是相当困难的该怎么办？三、分治法三、分治法（（ Divide and Conquer Divide and Conquer ）） 如何求解规模较大问题？如何求解规模较大问题？——分析问题的特征，寻找合适的解决问题的方法 分治法是求解较大规模问题的一种有效方法，并是很多高效算法的设计基础 2. 分治法的基本思想 分治法的设计思想是，将一个难以直接解决的、规模较大问题，分割成若干个规模较小、相对容易解决的、但性质相同的子问题，然后分别解决这些子问题在获得这些较小子问题的解之后，再将子问题的解合并成原始问题的解 ——这种算法设计策略叫做分治法。
具体的说，就是： 对于一个规模为n的问题，若规模较小，则直接解决；否则将其分解为k个规模较小的子问题，如果这些子问题还较大，则可以递归地将子问题分解为更小的子问题，直到子问题的规模足够小、可以直接求解为止，然后求解子问题，并在得到子问题的解之后逐级合并，最后得到原问题的解 原问题与子问题的求解是一个自然的递归过程，分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法 注：分治算法本身并不一定要用递归过程描述 可用分治法求解的问题一般应具有以下几个特征： 1) 该问题的规模缩小到一定的程度就可以容易地解决； 2) 该问题可以分解为若干个规模较小的“同质”问题； 3) 子问题的解可以最终合并为原始问题的解； 4) 每次分解出的子问题是相互独立的，子问题之间不包含公共的子“子问题” 分治法的三个基本步骤 ： 1）分解：将原问题分解为若干个规模较小、相互独立，但与原问题性质相同的子问题； 2）求解：若子问题规模较小、可直接求解时则直接解，否则递归地求解各个子问题 3）合并：将各个子问题的解合并为原问题的解。
在用分治策略时，子问题应该怎样分解才为适宜？子问题的规模应该怎样才为适当？ 实践经验告诉我们，在用分治法设计算法时，最好使子问题的规模大致相同，即将一个问题分成大小相等的k个子问题这种使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想，它几乎总是比子问题规模不等的做法要好 许多问题可以取 k=2，二分法是最常用的分治策略 3.3.分治策略的抽象化控制过程分治策略的抽象化控制过程————二分策略二分策略算法3.1 分治策略的抽象化控制procedure DANDC(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(DANDC(p,m), DANDC(m+1,q))) endifend DANDCØk=2：二分是最常用的分解策略；ØSMALL(p,q)：布尔函数，判断输入规模q-p+1是否足够小，是则无需再进一步分就可求解；ØG(p,q)： 当SMALL(p,q)为真时，对输入规模为q-p+1的子问题直接求解；ØDIVIDE(p.q)：当规模还较大时，进一步分解，返回[p,q]区间的分割点；ØDANDC(p,m)、DANDC(m+1,q)：递归求解ØCOMBINE(x,y)：结果合并函数最初的调用：DANDC(1,n) DANDC的计算时间 若所分成的两个子问题的规模大致相等，则DANDC总的计算时间可用递归关系式表示如下： g(n) n足够小 T(n) = 2T(n/2) + f(n) 否则 注：ØT(n)：表示输入规模为n时的DANDC计算时间Øg(n)：表示对足够小的输入规模直接求解的计算时间Øf(n)：表示COMBINE对两个子区间的子结果进行合并的时间 1. 1. 问题的描述问题的描述 已知一个按非降次序排列的元素表a1, a2, …,an，判定某给定的元素x是否在该表中出现。
Ø 若是，则找出x在表中的位置并返回其所在位置的下标Ø 若非，则返回0值3.23.2二分检索二分检索————折半查找折半查找 2. 2. 问题分析问题分析 1） 二分检索是有序表上的检索问题 2）给出一种问题的形式描述如下： I=(n, a1, a2, …,an,x) 3）选取下标k，由此将I分解为3个子问题： I1=(k-1, a1, a2, …,ak-1,x) I2=(1, ak,x) I3=(n-k, ak+1, a2, …,an,x)Ø 对于I2，若ak=x，则有解k，对I1、I3不用再求解；否则，Ø 若x
注： 给定一个按非降次序排列的元素数组A(1:n)，n≥1,判断x是否出现•若是，置j，使得x=A(j)•若非，j=0取中策略 例3.1：设A(1:9)=(-15，-6，0，7，9，23，54，82，101) 在A中检索x=101，-14，82执行轨迹见下表1表1 运行轨迹示例x=101x=-14x=82lowhighmidlowhighmidlowhighmid19519519569714269789811189899921找不到找到 找到 成功的检索不成功的检索成功的检索 1 2 3 4 5 6 7 8 9 BINSRCH(A,n,x,j)能正确地运行吗？1）在具体指定A中的数据元素及x的数据类型后，算法中的所有运算都能按要求正确执行——即首先满足确定性和能行性2）终止性问题 算法初始部分置low←1, high←n ① 若n=0，不进入循环，j置0，算法终止 ② 否则，进入循环，计算mid,Ø 或 x=A(mid)，j置为mid，算法终止；Ø 或x
1）空间特性 n+5个空间位置，分别存放A、x、j、 mid、low、high，所以空间复杂度为О(n)4.4.性能分析性能分析2) 时间特性 区分以下情况进行分析● 成功和不成功检索情况:Ø 成功检索：指所检索的x恰好在A中出现 由于A中共有n个元素，故成功检索恰好有n种可能的情况Ø 不成功检索：指x不出现在A中 根据取值情况，不成功检索共有n+1种可能性（用区间表示）： x
运算的频率计数的统计1. while循环体外语句的频 率计数为12. 集中考虑while循环中x与A 中元素的比较运算 ——其它运算的频率计数 与比较运算有相同的数量 级 3. case语句的分析：假定只 需一次比较就可确定case 语句控制是三种情况的哪 一种procedure BINSRCH(A,n,x,j) integer low,high,mid,j,n; low←1; high←n; while low≤high do mid ← case :x
可用一棵二元树描述这一过程，称为二元比较树（2）二元比较树的构成u结点：分为内结点和外结点两种 内结点：代表一次元素比较，用 圆形结 点表示，存放一个 mid值(下标)， 代表成功检索情况 外结点：用方形结点表示， 表示不成功 检索情况，本身不代表比较操作u路 径：代表检索中元素的比较序列u分 支：“小于”进入左分支， “大于” 进入右分支例3.1的二元比较树 二元比较树的查找过程p 若x在A中出现，则算法在一个圆形的内结点处结束p 若x不在A中出现，则算法在一个方形的外结点处结束 注：二元比较树中，外结点不代表元素的比较，因为比较过程在该外结点的上一级的内结点处已经结束 例3.1的二元比较树与x比较大于小于 关于二分检索时间复杂度的定理关于二分检索时间复杂度的定理定理3.1 若n在区域[2k-1,2k)中，则对于一次成功的检索， BINSRCH至多做k次比较；对于一次不成功的检索， 或者做k-1次比较，或者做k次比较。
证明要点证明要点：Ø比较过程： ►成功检索在内结点处结束，不成功检索在外结点处结束 ►成功检索在i级的某个内结点终止时，所需要的元素比较次数是i， 等于根到该内结点的路径长度＋1 ►不成功检索在i级的外部结点终止所需的元素比较次数是i-1， 等于根到该外结点的路径长度 证明要点之二证明要点之二：Ø 二分检索中，每次mid取中值，故其二元比较树是一种“结点平衡”的树： ★ 当2k-1≤n<2k时，结点分布情况为： 内结点：1至k级 外结点：k级或k+1级， ★ 外部结点在相邻的两级上 ——最深一层或倒数第2层 证明：证明：由于由于由于由于：n∈[2k-1,2k) k≈logn， 故，1）不成功检索 由于外结点在最末的两级上，故不成功检索的最好、最坏和平均情况的计算时间均为 2）成功检索 最好情况：根结点代表成功检索的最好情况，在第一级，故其计算时间为 最坏情况：最深一层的内结点代表成功检索的最坏情况，在第 级，故其计算时间为 这里利用外部结点和内部结点到根距离和之间的关系证明二分检索成功检索的平均计算时间为O(logn)。
由根到所有内结点的距离之和称为内部路径长度，记为I； 由根到所有外结点的距离之和称为外部路径长度，记为E则有关系， E=I+2n ................................ ① 记， U(n)是不成功检索的平均计算时间，则 U(n) = E/(n+1) ............... ② S(n)是成功检索的平均计算时间，则 S(n) = I/n + 1 ................③ 成功检索的平均情况下的计算时间是多少？ 由上面① ② ③得: S(n) = (1+1/n)U(n) -1 当n→∞,S(n) ∝ U(n) ，而U(n) = 所以 S(n) = 最后的结论： 证毕 成功检索最好 平均 最坏不成功检索最好 平均 最坏 以比较为基础的检索：算法中只允许使用元素间的比较运算， 而不允许对它们实施其它运算。
问题：A为n个元素的有序表，设A(1:n)，A(1)< A(2) < … < A(n)检索一给定元素x是否在A中出现 问：是否存在其它以元素比较为基础的检索算法，它的计 算时间在最坏情况下比二分检索有更低的数量级?4. 4. 以比较为基础检索的时间下界以比较为基础检索的时间下界 分析分析：任何以比较为基础的检索算法，其执行过 程都可以用二元比较树来描述内结点内结点：表示一次元素的比较，并代表：表示一次元素的比较，并代表成功检索成功检索情况每棵比较树中恰情况每棵比较树中恰 好含有好含有n n个内结点，分别与个内结点，分别与n n个不同个不同i i值相对应；值相对应；外结点外结点：代表不成功检索情况每棵比较树中恰好有：代表不成功检索情况每棵比较树中恰好有n+1n+1个外结点分别个外结点分别 与与n+1n+1中不成功检索情况相对应中不成功检索情况相对应 以比较为基础的有序检索问题最坏情况下的时间下界：定理3.1 设A(1:n)含有 n(n≥1)个不同的元素，且有 A(1) < A(2) < …< A(n)。
现以以比较为基础的算法去判断给定的x是否有 ，则，最坏情况下，任何这样的算法所 需的最小比较次数FIND(n)有：证明： ①从模拟求解检索问题算法的比较树可知，FIND(n)不大于树中由根到一个叶子（外部结点）的最长路经的距离 证明（续）： ②在所有的二元比较树中必定有n个内结点分别与x在A中的n中可能的出现相对应 ③如果一棵二元树的所有内结点所在的级数小于或等于k，则该树中最多有2k-1个内结点 故，n≤2k-1,即结论1）任何一种以比较为基础的有序检索算法，在最坏情况下 的计算时间都不低于Ο(logn)因此，不可能存在最坏 情况比二分检索数量级还低的算法2）二分检索是解决检索问题的最优的最坏情况算法 1. 查找问题： 1) 在元素表中查找给定的元素：二分检索，顺序查找 2) 在元素表找最大元素和最小元素 3) 在元素表找第一小（大）和第二小（大）元素 4) 找出元素表中的第k小元素等3.3 3.3 找最大和最小元素找最大和最小元素 例3.2 老板有一袋金块，共n块。
将有两名最优秀的雇员每人得到其中的一块，排名第一的得到最重的那块，排名第二的雇员得到袋子中最轻的金块假设有一台比较重量的仪器，我们希望用最少的比较次数找出最重和最轻的金块算法分析：该问题转化为在一个具有n个元素的数组里寻找 最大和最小元素问题 2.找最大和最小元素的算法方法一，直接比较数组遍历，将每个元素和当前最大元素和最小元素进行比较，记录新的最大元素和最小元素，直至遍历数组结束并返回最大元素和最小元素算法3.2 直接找最大和最小元素procedure STRAITMAXMIN(A,n,max,min)//将A中的最大值置于max，最小值置于min// Integer i,n max←min←A(1) for i←2 to n do if A(i) > max then max←A(i) endif if A(i) < min then min←A(i) endif repeatend STRAITMAXMIN 算法的性能： 在输入规模为n时，这个算法所执行的元素比较次数是2n-2。
问题：有没有更快的算法解决上述问题？ 用分治法设计一个解决上述问题的算法 方法二，分治求解 记问题的一个实例为：I = (n, a1… , an)采用二分法将I分成两个子集合进行处理： 和 则有， MAX(I) = max(MAX(I1),MAX(I2)) MIN(I) = min(MIN(I1),MIN(I2)) MAX(I)和MIN(I)分别代表I中元素的最大者和最小者采用递归的设计策略，得到以下算法： 找最大最小元素的递归算法找最大最小元素的递归算法算法3.4 递归求取最大和最小元素procedure MAXMIN(i,j,fmax,fmin) //A(1:n)是含有n个元素的全局数组，参数i,j是整数，1≤i,j≤n，代表当前的查找区间 // //该过程把A(i:j)中的最大和最小元素分别赋给fmax和fmin // integer i,j;global n,A(1:n) case :i=j: fmax←fmin←A(i) //只有一个元素 :i=j-1:if A(i)
已经达到了以元素比较为基础的找最大最小元素的算法计算时间的下界：2）存在的问题——递归调用造成： Ø空间占用量大 入栈参数：i, j, fmax, fmin和返回地址五个值 有 级的递归Ø时间可能不比预计的理想 如果元素A(i)和A(j)的比较与i和j的比较在时间上相差不大时，算法MAXMIN不可取 详见《计算机算法基础》 方法三，改进的方法一算法3.2-1 直接找最大和最小元素算法的改进procedure STRAITMAXMIN(A,n,max,min)//将A中的最大值置于max，最小值置于min// Integer i,n max←min←A(1) for i←2 to n do if A(i) > max then max←A(i) endif else if A(i) < min then min←A(i) endif repeatend STRAITMAXMIN 改进：最好的情况下只需要n-1次比较；但最坏的情 况下还是需要2(n-1)。
平均3(n-1)/2 策略：策略： 设fmin、fmax分别代表当前最小值和最大值然后成对地处理集合中的元素：每对元素先互相比较，然后把较小者与fmin比较，把较大者与fmax比较，根据情况修正fmin和fmax开始的时候置：开始的时候置：u 如果n为奇数，则将fmin=fmax=a1u 如果n为偶数，则fmin=min(a1,a2)，fmax=max(a1,a2)改进：改进： 这样的处理使得每二个元素比较三次即可，而不是每个元素都需要2次比较运算故至多 次比较就可同时找出最大、最小元素方法四：最坏情况为方法四：最坏情况为3n/23n/2的迭代算法的迭代算法 1. 1. 归并排序归并排序 首先将原始数组A中的元素分成两个子集合：A1(1: )和A2( +1 :n)分别对这两个子集合单独分类，然后将已分类的两个子序列归并成一个含有n个元素的、分类好的序列这样的一个分类过程称为归并分类3.4 3.4 基于分治的分类算法基于分治的分类算法 1 1）算法描述）算法描述算法算法3.4 3.4 归并分类算法归并分类算法procedure MERGESORT(low,high) //A(low:high)是一个全程数组，low和high分别指示当前待分类区间的最小下标和最大下标，含有high-low+1≥0个待分类的元素// integer low,high if low
2) 过程MERGESORT的分类时间用递推关系式表示如下: a n=1,a是常数 T(n)= 2T(n/2)+cn n>1, c是常数 化简: 若n=2k,则有, T(n) =2(2T(n/4)+cn/2)+cn = 4T(n/4) + 2cn =4T(2T(n/8) +cn/4) + 2cn = … =2kT(1)+kcn = an+cnlogn //k=logn// 若2k 分类就是确定1,2,…,n的一种排列P1,P2,…Pn,使得记录的关键字满足以下非递减（或非递增）排列关系 从而使n个记录成为一个按关键字排列有序的序列： (2)(2)以关键字比较为基础的分类算法的时间下界以关键字比较为基础的分类算法的时间下界 ——最坏情况下的时间下界为： 假设参加分类的n个关键字A(1),A(2),…,A(n)互异任意两个关键字的比较必导致A(i) 初始集合中的元素因顺序不同，将导致排序过程走不同的分支 现基于二元树的性质有：现基于二元树的性质有： ① 由于n个关键字有n!种可能的排列，所以分类的二元比较树中将有 n!个外部结点 每个外部结点代表一种特定的排列，该排列对应于某种特定输入情况下的分类序列 ② 设一棵二元比较树的所有内结点的级数均小于或等于k，则该树中最多有2k个外结点 记算法在最坏情况下所作的比较次数为T(n)，则有 T(n)=k —— 生成外结点所代表的分类序列所需的比较次数等于该外结点所在的级数-1； 则，根据①和②的分析，有： n!≤2T(n) 化简： 当n>1时，有n!≥n(n-1)(n-2)…( )≥(n/2)n/2 当n≥4时，有 T(n)≥(n/2)log(n/2)≥(n/4)logn 故，任何以比较为基础的分类算法的最坏情况的时间下界为： Ω(nlogn) 2.2.快速分类快速分类 快速分类是一种基于划分的分类方法。 划分：在待分类集合A中选取某元素t，按照与t的大小关系重新整理A中元素，使得整理后t被置于序列的某位置上，而在t以前出现的元素均小于等于t，在t以后的元素均大于等于t这一元素的整理过程称为划分（Partitioning） 划分元素：元素t被称为划分元素 快速分类：这种通过对待排序集合反复划分达到分类目的算法称为快速分类算法 1 1）算法描述）算法描述算法3.6 划划分过程（分过程（PARTITIONPARTITION）算法描述）算法描述procedure PARTITION(m,p) //用A(m)划分集合A(m:p-1) integer m,p,i; global A(m:p-1) v←A(m);i←m //A(m)是划分元素// loop loop i←i+1 until A(i)≥v repeat // i由左向右移// loop p←p-1 until A(p)≤v repeat //p由右向左移// if i
pivv 算法算法3.7 3.7 快速分类算法快速分类算法 procedure QUICKSORT(p,q) //将数组A(1:n)中的元素A(p),…A(q)按递增的方式分类 A(n+1)有定义，且假定A(n+1)←+∞// integer p,q;global n,A(1:n) if p 算法主体 不变之后，仍从A(m)开始执行划分操作 递归层次QuickSort(1,n)QuickSort(1,j1-1)QuickSort(j1-1,n)QuickSort(1,j21-1)QuickSort(j21+1, j1-1)QuickSort(j1-1,j22-1)QuickSort(j22+1,n)n个元素参加划分和分类去掉1个第一级的划分元素n-1个元素参加划分和分类去掉2个第二级的划分元素n-3个元素参加划分和分类去掉4个第三级的划分元素第一层第二层第三层 设在任一级递归调用上，调用PARTITION处理的所有元素总数为r，则，初始时r=n，以后的每级递归上，由于删去了上一级的划分元素，故r比上一级至少1：理想情况，第一级少1，第二级少2，第三级少4， …；最坏情况，每次仅减少1（每次选取的划分元素刚好是当前集合中最小或最大者） n 最坏情况分析最坏情况分析Ø 记最坏情况下的元素比较次数是Cw(n)；Ø PARTITION一次调用中的元素比较数是p-m+1，若一级递归调用上处理的元素总数为r，则 PARTITION的比较总数为O(r)。 最坏情况下（第i次调用Partition所得的划分元素恰好是第i小元素），每级递归调用的元素总数仅比上一级少1，故Cw(n)是r由n到2的累加和 即：Cw(n)= = Ο(n2) n 平均情况分析平均情况分析 平均情况是指集合中的元素以任意顺序排列，且任选元素作为划分元素进行划分和分类，在这些所有可能的情况下，算法执行性能的平均值 设调用PARTITION(m,p)时，所选取划分元素v恰好是A(m:p-1)中的第i小元素（1≤i≤p-m）的概率相等则经过一次划分，所留下的待分类的两个子文件恰好是A(m:j-1)和A(j+1:p-1)的概率是：1/(p-m), m≤j
当小的子文件分类完成后，再对大的子文件进行分类栈：需要一个栈空间保存目前暂不分类的较大子文件并在较小子文件分类完成后，从栈中退出最新的较大子文件进行下一步分类 pqjtopj＋1 算法3.8 QuickSort2(p,q) integer STACK(1:max),top //max=2 global A(1:n);local integer j top←0 loop while p 2）改进的插入分类算法 采用二分检索的原理，在待插入的元素左侧的已排序数组中查找插入位置即， 在插入第i个元素时，对前面的0～i-1元素进行折半，先跟它们的中间元素比，如果小，则对前半再进行折半，否则对后半进行折半，直到low > high，然后把第i个元素前与目标位置之间的所有元素后移，再把第i个元素放在目标位置上算法略）3. 3. 改进的插入分类算法改进的插入分类算法 3.5 选择问题选择问题1. 问题描述问题描述 在n个元素的表A(1:n)中找第k小元素，1≤k≤n注：A未经分类2. 设计思路设计思路 1）先排序，后查找）先排序，后查找 排序后第k位的元素即为待查找的元素 时间复杂度O(nlogn) 存在的问题存在的问题：有点浪费，排序涉及了太多k以外的元素 2）利用）利用PARTITION过程设计一个较低时间复杂度过程设计一个较低时间复杂度 的算法的算法 PARTITION(1，n)：在第一次划分后，划分元素v被放在位置A(j)上，则有j-1个元素小于或等于A(j)，且有n-j个元素大于或等于A(j)。 此时，Ø 若k=j，则A(j)即是第k小元素；否则，Ø 若k Ø 在执行一次PARTITION后，或者找到第k小元素，或者将 在缩小的子集(A(m,k-1)或A(k+1,j))中继续查找缩小 的子集的元素数比上一次划分的元素数至少少1 1) 1) 最坏情况最坏情况 SELECT的最坏情况时间是Ο(n2)最坏情况下的特例最坏情况下的特例： 输入A恰好使对PARTITION的第i次调用选用的划分元素是第i小元素，而k=n 此时，（区间下界）m随着PARTITION的每一次调用而仅增加1，j保持不变 PARTITION最终需要调用n次 则,n次调用的时间总量是 2)2) 平均情况 平均情况 设 是找A(1:n)中第k小元素的平均时间 是SELECT的平均计算时间，则有并定义则有：TA(n)≤R(n)对n个不同的元素，问题实例可能有n!种不同的情况综合考查所有情况后得到的平均值在所有可能的情况下，找所有可能的k小元素某个特定的k 定理定理3.3 SELECT的平均计算时间的平均计算时间TA(n)是是Ο(n)证明： PARTITION的一次执行时间是Ο(n)。 在随机等概率选择划分元素时，首次调用PARTITION中划分元素v刚好是A中第i小元素的概率为1/n，1≤i≤n 则，存在正常数c，c>0,有， n≥2 且有， n≥2 划分元素i 因此， 若m为偶数，则 若m为奇数，则 由于TA(n)≤R(n)，所以TA(n)≤4cn 故，TA(n)=Ο(n)1km-11m– k+1m-1 5. 5. 最坏情况是最坏情况是Ο Ο(n)(n)的选择算法的选择算法1）采用两次取中间值的规则精心选取划分元素）采用两次取中间值的规则精心选取划分元素 目标：精心选择划分元素，避免随机选取可能出现的极端情况 步骤：分三步 首先，将参加划分的n个元素分成 组，每组有r个元素(r≥1)多余的 个元素忽略不计） 然后，对这 组每组的r个元素进行分类并找出其中间元素mi,1≤i≤ ，共得 个中间值——一次取中 之后，对这 个中间值分类，再找出其中间值mm将mm作为划分元素执行划分——二次取中 n例：设 n=35, r=7• 分为n/r = 5个元素组： B1，B2，B3，B4，B5； 每组有7个元素• B1-B5按照各组的mi的非降次 序排列• mm = mi的中间值，1≤i≤5由图所示有：mm中间值小于等于mm的元素大于等于mm的元素非降次序B1 B2 B3 B4 B5按照mi的非降次序排列 mm中间值小于等于mm的元素大于等于mm的元素非降次序B1 B2 B3 B4 B5r个元素的中间值是第 小元素；至少有 个mi小于或等于mm；也至少有 个mi大于或等于mm。 故，至少有 个元素小于或等于mmmm中间值小于等于mm的元素大于等于mm的元素非降次序B1 B2 B3 B4 B5 mm中间值小于等于mm的元素大于等于mm的元素非降次序B1 B2 B3 B4 B5 同理，也至少有 个元素大于或等于mm 以以r=5r=5为例使用两次取中间值规则来选择划分元素v(即mm)，可得到，u 至少有 个元素小于或等于选择元素vu 且至多有 个元素大于等于v mm中间值小于等于mm的元素大于等于mm的元素非降次序B1 B2 B3 B4 B5 同理同理，u 至少有 个元素大于或等于选择元素vu 且至多有 个元素小于等于v mm中间值小于等于mm的元素大于等于mm的元素非降次序B1 B2 B3 B4 B5 故故， 这样的v可较好地划分A中的n个元素：比足够多的元素大，也比足够多的元素小，不论落在那个区域，总可以在下一步查找前舍去足够多的元素，而在剩下的“较小”范围内继续查找。 mm中间值小于等于mm的元素大于等于mm的元素非降次序B1 B2 B3 B4 B5 2 2）算法描述）算法描述算法3.10 使用二次取中规则的选择算法的说明性描述 Procedure SELECT2(A,k,n) //在集合A中找第k小元素 ① 若n≤r，则采用插入排序法直接对A分类并返回第k小元素否则 ② 把A分成大小为r的 个子集合，忽略多余的元素 ③ 设M={m1,m2,…m }是 子集合的中间值集合 ④ v←SELECT2(M, , ) ⑤ j←PARTITION(A，v) ⑥ case :k=j: return(v) :k 假定A中的元素各不相同，则有 ① 若n≤r，则采用插入法直接对A分类并返回第k小元素 →Ο(1) ② 把A分成大小为r的 个子集合，忽略多余的元素 →Ο(n) ③ 设M={m1,m2,…mr }是 子集合的中间值集合 →Ο(n) ④ v←SELECT2(M, , ) →T(n/5) ⑤ j←PARTITION(A，v) →Ο(n) ⑥ case →T(3n/4),当n≥24 :k=j: return(v) :k 故有， cn n ＜ 24, T(n)＝ T(n/5)+T(3n/4)+cn n≥24用归纳法可证： T(n)≤20cn 故，在r=5地情况下，求解n个不同元素选择问题的算法SELECT2的最坏情况时间是Ο(n) 进一步分析： 若A中有相同的元素时，上述结论T(n)=O(n)可能不成立原因： 步骤⑤经PARTITION调用所产生的S和R两个子集合中可能存在一些元素等于划分元素v,可能导致|S|或|R|大于0.7n+1.2，从而影响到算法的效率例如： 设r=5,且A中有相同元素不妨假设其中有0.7n+1.2个元素比v小，而其余的元素都等于v 则，经过PARTITION，这些等于v的元素中至多有一半可能在落在S中，故|S|≤0.7n+1.2+(0.3n-1.2)/2=0.85n+0.6 同理，|R|≤0.85n+0.6 可得，此时步骤④和⑥所处理的元素总数将是 T(n/5)+T(0.85n+0.6)≈1.05n+0.6>n 不再是线性关系。 故有T(n)≠Ο(n) 改进： 方法一：将A集合分成3个子集合U,S和R，其中U是由A中所有与v相同的元素组成，S是由A中所有比v小的元素组成，R则是A中所有比v大的元素组成 同时步骤⑥更改： case :|S|≥k:return(SELECT2(S,k,|S|) :|S|+|U|≥k:return(v) :else: return(SELECT2(R,k-|S|-|U|,|R|)) endcase 从而保证 |S|和|R|≤0.7n+1.2成立，故关于T(n)的分析仍然成立 T(n) = Ο(n) 方法二：选取其他的r值进行计算 取r=9重新计算可得，此时将有 个元素小于或等于v，同时至少有 大于或等于v 则 当n≥90时，|S|和|R|都至多为 基于上述分析，有新的递推式：相等元素的一半 c1n n＜90 T(n) ＝ T(n/9)+T(63n/72)+c1n n≥90 用归纳法可证： T(n)≤72c1n 即，T(n) = Ο(n) 算法中需要解决的两个问题 1) 如何求子集合的中间值？ 当r较小时，采用INSERTIONSORT(A,i,j)直接对每组的r个元素分类，在分类好的序列中，中间元素即为中间下标位置所对应的元素。 2) 如何保存 个子集合的中间值？ 在各组找到中间元素后，将其调整到数组A的前部，按子集合的顺序关系连续保存从而可方便用递归调用的方式对这些中间值进行排序并找出中间值的中间值（即，二次取中） 4 4））SELECT2SELECT2的实现的实现 算法3.11 SELECT2算法的实现 procedure SEL(A,m,p,k) //返回一个i，使得i∈[m,p]，且A(i)是A(m:p)中第k小元素，r是一个全程变量，其取值为大于1的整数 global r; integer n,i,j loop if p-m+1≤r then call INSERTIONSORT(A,m,p); return (m+k-1); endif n←p-m+1 //元素数// for i←1 to do //计算中间值// call INSERTIONSORT(A,m+(i-1)*r,m+i*r-1) //将中间值收集到A(m:p)的前部// call INTERCHANGE(A(m+i-1),A(m+(i-1)r + -1)) repeat j←SEL(A,m,m+ -1, )//mm// call INTERCHANGE (A(m),A(j)) //产生划分元素，将之调整到第一个元素// j←p+1 call 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 SEL 算法3.12 SELECT2算法实现的递归程序描述 procedure SEL(A,m,p,k) //返回一个i，使得i∈[m,p]，且A(i)是A(m:p)中第k小元素，r是一个全程变量，其取值为大于1的整数 global r; integer n,i,j if p-m+1≤r then call INSERTIONSORT(A,m,p); return (m+k-1); endif n←p-m+1 //元素数// for i←1 to do //计算中间值// call INSERTIONSORT(A,m+(i-1)*r,m+i*r-1) //将中间值收集到A(m:p)的前部// call INTERCHANGE(A(m+i-1),A(m+(i-1)r + -1)) repeat j←SEL(A,m,m+ -1, )//mm// call INTERCHANGE (A(m),A(j)) //产生划分元素，将之调整到第一个元素// j←p+1 call PARTITION(m,j) case :j-m+1=k: return j :j-m+1>k: return SEL(A,m,j-1,k) :else: return SEL(A,j+1,p,k-(j-m+1)) endcaseend SEL 3.6 矩阵乘积的Strassen算法1. 回顾一下矩阵运算 已知两个n阶方阵： A＝(aij)nxn , B＝(bij)nxn 1）矩阵加法 C＝A＋B＝ (cij)nxn ，其中, 计算量：Θ(n2) 2）矩阵乘法 C＝AB＝ (cij)nxn ，其中， 计算量：〇(n3)。 共有n2个cij需要计算，每个cij需要n 次乘运算,n-1次加法问：是否可以用少于n3次乘法完成C的计算? 1969年Strassen： n2.81 2. 矩阵乘法 例 2X2的两个矩阵，直接相乘的计算过程如下： 故，A、B直接相乘，需要8次乘法和4次加法 StrassenStrassen的计算方法：的计算方法： 令： P=(a11+a22)(b11+b22) Q=(a21+a22) b11 R=a11 (b12-b22) S=a22 (b21-b11) T=(a11 + a12)b22 U=(a11 – a21) (b11 + b12) V=(a12 – a22) (b21 + b22) 则， c11=P+S-T+V = (a11+a22)(b11+b22) + a22 (b21-b11) -(a11 + a12)b22+(a12 – a22) (b21 + b22) ≡ a11b11+a12b21 c12=R+T ≡ a11b12+a12b22 c21=Q+S ≡ a21b11+a22b21 c22=P+R-Q-U ≡ a21b12+a22b22 Strassen计算方法的分析： 令： P=(a11+a22)(b11+b22) Q=(a21+a22) b11 R=a11 (b12-b22) S=a22 (b21-b11) T=(a11 + a12)b22 U=(a11 – a21) (b11 + b12) V=(a12 – a22) (b21 + b22) 则， c11=P+S-T+V c12=R+T c21=Q+S c22=P+R-Q-U计算量：计算量： 乘法次数：7次 加（减）法次数：18次特点：特点： 增加了加（减）法计算量，减少了乘法计算量带来的改进：带来的改进： 直观上，在用程序完成的计算中，通常认为乘法运算比加法运算需要更多的时间，Strassen矩阵乘通过减少乘法计算量、适当增加加法计算量，从总体上减少矩阵乘的运算时间。 到底能减少多少呢？ StrassenStrassen矩阵乘法的一般形式矩阵乘法的一般形式（1969年Strassen ） 设 n＝ 2k ，两个n阶方阵为 A＝(aij)nxn B＝(bij)nxn （注：若n≠2k ，可通过在A和B中补0使之变成阶是2的幂的方阵） 首先，将A和B分成4个(n/2)x(n/2)的子矩阵： 对比对比：简单矩阵分块相乘：简单矩阵分块相乘 8次(n/2)x(n/2) 矩阵乘 4次(n/2)x(n/2) 矩阵加 任意两个子矩阵块的乘可以沿用同样的规则继续下去，即：如果子矩阵的阶大于2，则将子矩阵分成更小的子矩阵，直到每个子矩阵只含一个元素为止 ——从而可以构造出一个递归计算过程 时间分析：时间分析： 令T(n)表示两个nxn矩阵相乘的计算时间，则首次分块时，需要： 1) 8次(n/2)x(n/2) 矩阵乘 －－－－－>8T(n/2) 2) 4次(n/2)x(n/2) 矩阵加 －－－－－>dn2 故， 其中，b，d是常数 化简：T(n) = O(n3) StrassenStrassen矩阵乘的一般方法（矩阵乘的一般方法（分块分块））令 P=(A11+A22)(B11+B22) Q=(A21+A22) B11 R=A11 (B12-B22) S=A12 (B21-B11) T=(A11 + A12)B22 U=(A11 – A21) (B11 + B12) V=(A12 – A22 ) (B21 + B22) 则， C11=P+S-T+V C12=R+T C21=Q+S C22=P+R-Q-U计算量：(n/2)x(n/2) 矩阵乘法：7次(n/2)x(n/2) 矩阵加法：18次 注：Strassen矩阵乘也是一个递归求解过程， 任意两个子矩阵块的乘可以沿用同样的规则进行。 StrassenStrassen矩阵乘法的计算复杂度分析矩阵乘法的计算复杂度分析 令T(n)表示两个n=2k阶矩阵的Strassen矩阵乘所需的计算时间，则有： b n≤2 T(n) = 7T(n/2) + an2 n＞2 其中， a和b是常数 化简： T(n) = an2(1+7/4+(7/4)2+…+(7/4)k-1) + 7kT(1) ≤ cn2(7/4)logn+7logn ＝ cn2nlog(7/4) + nlog7 ＝ cnlog4+log7-log4 + nlog7 ＝ (c+1)nlog7 ＝ Ο(nlog7)≈Ο(n2.81) #include 分成阶数相同的四个子矩阵，即分治思想 for(int i=0; i 理论意义大于实际意义 3.7 3.7 最近点对问题最近点对问题1. 问题描述 已知平面上分布着点集P中的n个点p1,p2,...pn，点i的坐标记为(xi,yi)，1≤i≤n两点之间的距离取其欧式距离，记为 问题：找出一对距离最近的点注：允许两个点位于同一个位置，此时两点之间的距离为0 平面上分布的点集pipj 分析：分析： 一种全搜索的方法：对每对点都计算距离，然后比较大小，找出其中的最小者 该方法的时间复杂度为：Ø 计算点间距离： O(n2)，因为需要计算n(n-1)/2对 点间的距离Ø 找最小距离：O(n2)，因为需要n(n-1)/2-1次比较 所以，总的时间复杂度：O(n2)问：有没有更好的办法？有没有更好的办法？ 2.2.求解最近点对问题的分治方法求解最近点对问题的分治方法 这里，利用分治法设计一个具有O(nlogn)时间复杂度的算法求解最近点对问题设计策略：设计策略： 1）首先将所有的点按照x坐标排序排序过程需要O(nlogn)的时间，不会从整体上增加时间复杂度的数量级。 2）划分：由于点已经按x坐标排序，所以空间上可以“想象” 画一条垂线，作为分割线，将点集分成左、右两半PL和PR 则，最近的一对点或者在PL中，或者在PR中，或者一个在PL中而另一个在PR中（跨越分割线）记, dL:PL中的最近点对距离； dR:PR中的最近点对距离； dC:跨越分割线的最近点对距离dLdCdR分割线PLPR 建立一个递归过程求dL和dR，并在此基础上计算dC而且，要使得dC的计算至多只能花O(n)的时间 这样，递归过程将由两个大致相等的一半大小的递归调用和O(n)附加工作组成，总的时间就可以控制在O(nlogn)以内（事实上，我们希望该时间达到O(nlogn)） 基于上述思想的算法流程大致描述如下： (1)做分割线（垂线）将点集分为PL和PR两部分 (2)递归地在PL中的找具有dL的点对 (3)递归地在PR中的找具有dR的点对 (4)在跨越分割线的点对中找具有dC的点对 (5)返回min(dL,dR,dC)对应的点对。 该如何实现？该如何实现？ 令δ=min(dL,dR)，通过观察可得，如果dC< δ，则dC对应的点对必然在分割线两侧的δ 距离以内，如图所示把这个区域叫做带(strip)从而，对dC的搜索只限制在strip区域内即可，限定了需要考虑的点的个数dLp1dRδδp2p3p6p4d5strip 3）计算dC方法一：对均匀分布的大型点集，可预计位于该带中的点的个数均匀而“稀疏”，平均只有 个点在这个带中因此，可以O(n)的时间计算出这些点对之间的距离描述如下： for i=1 to numPointsInStrip do for j=i+1 to numPointsInStrip do if dist(pi,pj)<δ δ = dist(pi,pj); 这里，numPointsInStrip = 方法一存在的问题方法一存在的问题：： 在最坏的情况下，所有的点可能都在Strip内因此，该方法不能总以线性时间运行。 如何改进？如何改进？ 事实上，确定dC的两个点的y坐标相差最多也不大于δ，否则dC>δ dC≤δΔx ≤ δΔy ≤ δ 计算dC的改进： 设点按它们的y坐标排序，如果pi和某个pj的y坐标相差大于δ，那么这样的pi可以终止计算，继续处理pi+1改进的算法描述如下： for i=1 to numPointsInStrip do for j=i+1 to numPointsInStrip do if pi and pj 's y-coordinates differ by more than δ break; else if dist(pi,pj)<δ δ = dist(pi,pj); 分析： 上述改进对运算时间的影响是显著的，因为对每一个pi，在pi和pj的y坐标相差大于δ时就会退出内层循环，这一过程中仅有少数的点pj被考察，大大减少了计算量。 如， dLp1dRδδp2p3p6p4d5δ对于p3只有两个点p4和p5落在垂直距离δ之内的带状区域中 一般情况：对于任意的点pi，在最坏情况下，最多有7个点pj需要考虑 这是因为，pi和pj点必定落在该带状区域左半部分的δXδ方块内，或者落在该带状区域右半部分的δXδ方块内最坏情况下，每个方块包含4个点，分别落在四个角上，并且其中一个是pi，另外7个就是需要考虑的pj点如图所示，左半部分(λx λ)右半部分(λxλ)PL1PL2PL3PL4PR1PR2PR3PR4 这样，对于每个pi，有最多7个点pj要考虑，所以对每个pi的计 算时间可看作是O(1)的则，计算比δ 好的dC的时间就 为O(n)于是得：最近点对求解过程由两个一半大小的递归调用加上合 并两个结果的线性附加工作组成，那么最近点对问题就 可以得到O(nlogn)的解了吗？还有问题需要讨论：还有问题需要讨论：点y坐标的排序问题 问题所在：如果每次递归都要对点的y坐标进行排序，则这又要有O(nlogn)的附加工作总的时间为 可得，整个算法的时间复杂度就为O(nlog2n)。 如何处理？ 进一步改进进一步改进：改进对点的坐标进行排序的处理方法策略策略：设置两个表， ◆ P表：按x坐标对点排序得到的表； ◆ Q表：按y坐标对点排序得到的表 这两个表可以在预处理阶段花费O(nlogn)时间得到再记，PL和QL是传递给左半部分递归调用的参数表， PR和QR是传递给右半部分递归调用的参数表首先：在使用上述策略将P分为两个部分之后，复制Q到QL和 QR中，然后删除QL和QR中不在各自范围内的点，这一 操作花费O(n)时间即可完成而此时QL和QR均已按y坐 标排好序 然后：将PL、PR和上面的QL、QR带入递归过程进行处理，PL、 PR是按照x坐标排序的点集，QL、QR是按照y坐标排序 的点集最后：当递归调用返回时，扫描Q表，删除其x坐标不在带内的 所有点此时Q中就只含有带中的点，而且这些点已是 按照y坐标排好序了的这一处理需要O(n)的时间。 综上所述综上所述，所有附加工作的总时间为O(n)，则整个算法的 计算时间为 作业题：1. 棋盘覆盖问题 在一个2k x 2k 个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘如图1所示，蓝色的为特殊方格： 棋盘覆盖问题是指，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖 试用分治法设计一个求解棋盘覆盖问题的算法图1 特殊棋盘，蓝色的为特殊方格图2 四中L形骨牌 2.大整数乘积 大整数（big integer）：位数很多的整数，普通的计算机不能直接处理，如： 9834975972130802345791023498570345 显然，这样的整数普通的计算机和程序语言是无法直接表示的 大整数运算：给定两个n位的整数I，J, 加、减法：可以用O(n)的时间计算出I+J和I-J，即使I、J是大整数； 乘法：若I、J超过普通计算机可以表示的数据范围，怎么计算IxJ? 如 I = 9834975972135791023498570345 J = 3432450018098972347892345023 方法一：按照小学数学的方法，“列算式”直接求解。 适当地编制算法，可以实现大整数乘，但时间复杂度为O(n2)方法二：利用分治法设计一个计算两个n二进制位的大整数相乘的算法，要求计算时间低于O(n2)分析你所给出的算法的时间复杂度 3. 《计算机算法基础》P99，4.54. 《计算机算法基础》P100，4.205. 《计算机算法基础》P100，4.25 。
