算法设计与分析(三)-分治法.ppt

算法设计与分析 2011.9 (acm创新实验班),“分而治之”的问题求解策略。 3.1 一般方法 1. 问题的提出 用计算机进行问题求解时，如果问题的规模n很小，可以直接求解，如排序问题， 当n=1时，不需任何计算即可完成。 当n=2时，作一次比较即可。 当n=3时，作3次比较也可完成， 当n比较大时，问题求解就不那么容易了。 一般情况下，要想直接解决一个规模较大的问题，有时是相当困难的。该怎么办？,三、分治法（ divide and conquer ）,如何求解规模较大问题？ 分析问题的特征，寻找合适的解决问题的方法 分治法是求解较大规模问题的一种有效方法，并是很多高效算法的设计基础。,2. 分治法的基本思想 分治法的设计思想是，将一个难以直接解决的、规模较大问题，分割成若干个规模较小、相对容易解决的、但性质相同的子问题，然后分别解决这些子问题。在获得这些较小子问题的解之后，再将子问题的解合并成原始问题的解。 这种算法设计策略叫做分治法。,具体的说，就是： 对于一个规模为n的问题，若规模较小，则直接解决；否则将其分解为k个规模较小的子问题，如果这些子问题还较大，则可以递归地将子问题分解为更小的子问题，直到子问题的规模足够小、可以直接求解为止，然后求解子问题，并在得到子问题的解之后逐级合并，最后得到原问题的解。 原问题与子问题的求解是一个自然的递归过程，分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。 注：分治算法本身并不一定要用递归过程描述。,可用分治法求解的问题一般应具有以下几个特征： 1) 该问题的规模缩小到一定的程度就可以容易地解决； 2) 该问题可以分解为若干个规模较小的“同质”问题； 3) 子问题的解可以最终合并为原始问题的解； 4) 每次分解出的子问题是相互独立的，子问题之间不包含公共的子“子问题”。,分治法的三个基本步骤 ： 1）分解：将原问题分解为若干个规模较小、相互独立，但与原问题性质相同的子问题； 2）求解：若子问题规模较小、可直接求解时则直接解，否则递归地求解各个子问题 3）合并：将各个子问题的解合并为原问题的解。,在用分治策略时，子问题应该怎样分解才为适宜？子问题的规模应该怎样才为适当？ 实践经验告诉我们，在用分治法设计算法时，最好使子问题的规模大致相同，即将一个问题分成大小相等的k个子问题。这种使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想，它几乎总是比子问题规模不等的做法要好。 。 许多问题可以取 k=2，二分法是最常用的分治策略。,3.分治策略的抽象化控制过程二分策略,算法3.1 分治策略的抽象化控制 procedure dandc(p,q) global n.a(1:n); integer m,p,q; /1pqn/ if small(p,q) then return(g(p,q) else mdivide(p,q) /pmq/ return(combine(dandc(p,m), dandc(m+1,q) endif end 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. 问题的描述 已知一个按非降次序排列的元素表a1, a2, ,an，判定某给定的元素x是否在该表中出现。 若是，则找出x在表中的位置并返回其所在位置的下标 若非，则返回0值。,3.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不用再求解；否则， 若xak，则只在i3中求解，对i1不用求解； 对i1 、i3的求解可再次采用分治方法求解,规模较大,规模足够小,规模较大,递归过程,算法3.1 二分检索 procedure binsrch(a,n,x,j) integer low,high,mid,j,n; low1; highn; while lowhigh do mid case :xa(mid):low mid+1 :else:jmid;return endcase repeat j0 end binsrch,3. 二分检索 二分检索：每次选取中间元素的下标进行分解。,注： 给定一个按非降次序排列的元素数组a(1:n)，n1,判断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 2 3 4 5 6 7 8 9,binsrch(a,n,x,j)能正确地运行吗？ 1）在具体指定a中的数据元素及x的数据类型后，算法中的所有运算都能按要求正确执行即首先满足确定性和能行性 2）终止性问题 算法初始部分置low1, highn 若n=0，不进入循环，j置0，算法终止 否则，进入循环，计算mid, 或 x=a(mid)，j置为mid，算法终止； 或xa(mid)，置lowmid+1，进入下次循环；搜索范围实际缩小为mid+1, high，对low, mid-1区间不做进一步搜索； 因low, high, mid都是整型变量，故按照上述规则，在有限步内，或找到某个mid，有a(mid) = x；或变得lowhigh，在a中没有找到任何元素等于x，算法终止。,1）空间特性 n+5个空间位置，分别存放a、x、j、 mid、low、high，所以空间复杂度为(n)。,4.性能分析,2) 时间特性 区分以下情况进行分析 成功和不成功检索情况: 成功检索：指所检索的x恰好在a中出现。 由于a中共有n个元素，故成功检索恰好有n种可能的情况 不成功检索：指x不出现在a中。 根据取值情况，不成功检索共有n+1种可能性（用区间表示）： xa(n),最好、最坏、平均检索情况 最好情况：最少几次运算就能达到目的。 执行步数最少，计算时间最短。 成功检索的最好情况：若x恰好是a中的某个元素，最少 几次确定x在a中的出现位置：1次 不成功检索的最好情况：若x不是a中的任何元素，最少 几次能判断出这一结论 最坏情况：最多几次运算才能达到目的。 执行步数最多，计算时间最长。 平均情况：典型数据配置下的执行情况，一般为各种情 况下计算时间的平均值。,运算的频率计数的统计 1. while循环体外语句的频 率计数为1 2. 集中考虑while循环中x与a 中元素的比较运算 其它运算的频率计数 与比较运算有相同的数量 级。 3. case语句的分析：假定只 需一次比较就可确定case 语句控制是三种情况的哪 一种。,procedure binsrch(a,n,x,j) integer low,high,mid,j,n; low1; highn; while lowhigh do mid case :xa(mid):low mid+1 :else:jmid;return endcase repeat j0 end binsrch,实例分析（例3.1）,每种查找情况所需的元素比较次数统计如下：,a 元素 -15 -6 0 7 9 23 54 82 101 成功检索比较次数 3 2 3 4 1 3 2 3 4 不成功检索比较次数 3 3 3 4 4 3 3 3 4 4,成功检索 最好：1次 最坏：4次 平均：（3+2+3+4+1+3+2+3+4）/92.77次 不成功检索 最好：3次 最坏：4次 平均：(3+3+3+4+4+3+3+3+4+4)/10 = 3.4次,基于二元比较树的分析,（1）什么是二元比较树？ 算法过程的主体是x与一系列中间元素a(mid)比较运算。可用一棵二元树描述这一过程，称为二元比较树 （2）二元比较树的构成 结点：分为内结点和外结点两种 内结点：代表一次元素比较，用 圆形结 点表示，存放一个 mid值(下标)， 代表成功检索情况。 外结点：用方形结点表示， 表示不成功 检索情况，本身不代表比较操作。 路 径：代表检索中元素的比较序列 分 支：“小于”进入左分支， “大于” 进入右分支。,例3.1的二元比较树,二元比较树的查找过程 若x在a中出现，则算法在一个圆形的内结点处结束 若x不在a中出现，则算法在一个方形的外结点处结束 注：二元比较树中，外结点不代表元素的比较，因为比较过程在该外结点的上一级的内结点处已经结束。,例3.1的二元比较树,与x比较,大于,小于,关于二分检索时间复杂度的定理 定理3.1 若n在区域2k-1,2k)中，则对于一次成功的检索， binsrch至多做k次比较；对于一次不成功的检索， 或者做k-1次比较，或者做k次比较。 证明要点： 比较过程： 成功检索在内结点处结束，不成功检索在外结点处结束 成功检索在i级的某个内结点终止时，所需要的元素比较次数是i， 等于根到该内结点的路径长度1。 不成功检索在i级的外部结点终止所需的元素比较次数是i-1， 等于根到该外结点的路径长度。,证明要点之二： 二分检索中，每次mid取中值，故其二元比较树是一种“结点平衡”的树： 当2k-1n2k时，结点分布情况为： 内结点：1至k级 外结点：k级或k+1级， 外部结点在相邻的两级上 最深一层或倒数第2层,证明： 由于：n2k-1,2k) klogn， 故，,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. 以比较为基础检索的时间下界,分析：任何以比较为基础的检索算法，其执行过 程都可以用二元比较树来描述。,内结点：表示一次元素的比较，并代表成功检索情况。每棵比较树中恰 好含有n个内结点，分别与n个不同i值相对应； 外结点：代表不成功检索情况。每棵比较树中恰好有n+1个外结点分别 与n+1中不成功检索情况相对应。,以比较为基础的有序检索问题最坏情况下的时间下界： 定理3.1 设a(1:n)含有 n(n1)个不同的元素，且有 a(1) a(2) a(n)。 现以以比较为基础的算法去判断给定的x是否有 ，则，最坏情况下，任何这样的算法所 需的最小比较次数find(n)有：,证明： 从模拟求解检索问题算法的比较树可知，find(n)不大于树中由根到一个叶子（外部结点）的最长路经的距离。,证明（续）： 在所有的二元比较树中必定有n个内结点分别与x在a中的n中可能的出现相对应。 如果一棵二元树的所有内结点所在的级数小于或等于k，则该树中最多有2k-1个内结点。 故，n2k-1,即,结论 1）任何一种以比较为基础的有序检索算法，在最坏情况下 的计算时间都不低于(logn)。因此，不可能存在最坏 情况比二分检索数量级还低的算法。 2）二分检索是解决检索问题的最优的最坏情况算法,1. 查找问题： 1) 在元素表中查找给定的元素：二分检索，顺序查找 2) 在元素表找最大元素和最小元素 3) 在元素表找第一小（大）和第二小（大）元素 4) 找出元素表中的第k小元素等,例3.2 老板有一袋金块，共n块。将有两名最优秀的雇员每人得到其中的一块，排名第一的得到最重的那块，排名第二的雇员得到袋子中最轻的金块。假设有一台比较重量的仪器，我们希望用最少的比较次数找出最重和最轻的金块。 算法分析：该问题转化为在一个具有n个元素的数组里寻找 最大和最小元素问题。,2.找最大和最小元素的算法 方法一，直接比较。数组遍历，将每个元素和当前最大元素和最小元素进行比较，记录新的最大元素和最小元素，直至遍历数组结束并返回最大元素和最小元素。,算法3.2 直接找最大和最小元素 procedure straitmaxmin(a,n,max,min) /将a中的最大值置于max，最小值置于min/ integer i,n maxmina(1) for i2 to n do if a(i) max then maxa(i) endif if a(i) min then mina(i) endif repeat end 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是整数，1i,jn，代表当前的查找区间 / /该过程把a(i:j)中的最大和最小元素分别赋给fmax和fmin / integer i,j;global n,a(1:n) case :i=j: fmaxfmina(i) /只有一个元素 :i=j-1:if a(i)a(j) then fmaxa(j);fmina(i) else fmaxa(i);fmina(j) /两个元素的情况 endif :else: mid /取中，并在两个子区间上作递归调用 call maxmin(i,mid,gmax,gmin) call maxmin(mid +1,j,hmax,hmin) fmaxmax(gmax,hmax); fminmin(gmin,hmin) end case end maxmin,maxmin过程的性能分析 0 n=1 t(n) = 1 n=2 n2 当n是2的幂时(n=2k),化简上式有， t(n)=2t(n/2) +2 =2(2t(n/4) + 2) + 2 =2k-1t(2) + =2k-1+2k-2 =3n/2-2,性能比较 1）与straitmaxmin算法相比，比较次数减少了25%（3n/2-2 : 2n-2)。已经达到了以元素比较为基础的找最大最小元素的算法计算时间的下界： 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 maxmina(1) for i2 to n do if a(i) max then maxa(i) endif else if a(i) min then mina(i) endif repeat end straitmaxmin 改进：最好的情况下只需要n-1次比较；但最坏的情 况下还是需要2(n-1)。平均3(n-1)/2。,策略： 设fmin、fmax分别代表当前最小值和最大值。然后成对地处理集合中的元素：每对元素先互相比较，然后把较小者与fmin比较，把较大者与fmax比较，根据情况修正fmin和fmax。 开始的时候置： 如果n为奇数，则将fmin=fmax=a1 如果n为偶数，则fmin=min(a1,a2)，fmax=max(a1,a2) 改进： 这样的处理使得每二个元素比较三次即可，而不是每个元素都需要2次比较运算。故至多 次比较就可同时找出最大、最小元素。,方法四：最坏情况为3n/2的迭代算法,1. 归并排序 首先将原始数组a中的元素分成两个子集合：a1(1: )和a2( +1 :n)。分别对这两个子集合单独分类，然后将已分类的两个子序列归并成一个含有n个元素的、分类好的序列。这样的一个分类过程称为归并分类。,3.4 基于分治的分类算法,1）算法描述 算法3.4 归并分类算法 procedure mergesort(low,high) /a(low:high)是一个全程数组，low和high分别指示当前待分类区间的最小下标和最大下标，含有high-low+10个待分类的元素/ integer low,high if lowhigh then /当含有2个及2个以上的元素时，作划分与递归处理/ mid /计算中分点/ call mergesort(low,mid) /在第一个子集合上分类(递归)/ call mergesort(mid+1,high) /在第二个子集合上分类(递归)/ call merge(low,mid,high) /归并已分类的两子集合/ endif end mergesort,算法3.5 使用辅助数组归并两个已分类的集合 procedure 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;/lowmidhigh/ global a(low,high);local b(low,high) hlow;ilow; jmid+1; while hmid and jhigh do /当两个集合都没有取尽时,将较小的元素先存放到b中/ if a(h)a(j) then b(i) a(h);hh+1 /如果前一个数组中的元素较小/ else b(i) a(j); jj+1 /如果后一个数组中的元素较小/ endif ii+1 repeat /处理尚有剩余元素的集合/ if hmid then for kj to high do b(i) a(k);ii+1; repeat else for kh to mid do b(i) a(k);ii+1; repeat endif for k low to high do a(k) b(k) repeat /将已归并的集合复制到a中/ end merge,2）性能分析 (1) 过程merge的归并时间与两数组元素的总数成正比，可表示为：cn。 (2) 过程mergesort的分类时间用递推关系式表示如下: a n=1,a是常数 t(n)= 2t(n/2)+cn n1, 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/ 若2kn2k+1，则有t(n)t(2k+1)。 所以得：t(n) = (nlogn),3）一般讨论：以比较为基础分类的时间下界,（1）分类的“本质” 给定n个记录r1,r2,rn，其相应的关键字是k1,k2,kn。 分类就是确定1,2,n的一种排列p1,p2,pn,使得记录的关键字满足以下非递减（或非递增）排列关系 从而使n个记录成为一个按关键字排列有序的序列：,(2)以关键字比较为基础的分类算法的时间下界 最坏情况下的时间下界为： 假设参加分类的n个关键字a(1),a(2),a(n)互异。任意两个关键字的比较必导致a(i)a(j)的结果。,利用二元比较树描述元素间的比较过程： 若a(i)a(j)，进入下一级的右分支,算法在外部结点终止。 从根到某外结点的路径代表某个特定输入情况下一种唯一的分类排序序列。路径长度表示生成该序列代表的分类表所需要的比较次数。而最长的路径代表算法在最坏情况下的执行情况，该路径的长度即是算法在最坏情况下所作的比较次数。 故，以比较为基础的分类算法的最坏情况下界等于二元比较树的最小高度。,初始集合中的元素因顺序不同，将导致排序过程走不同的分支,现基于二元树的性质有： 由于n个关键字有n!种可能的排列，所以分类的二元比较树中将有 n!个外部结点。 每个外部结点代表一种特定的排列，该排列对应于某种特定输入情况下的分类序列。 设一棵二元比较树的所有内结点的级数均小于或等于k，则该树中最多有2k个外结点。 记算法在最坏情况下所作的比较次数为t(n)，则有 t(n)=k 生成外结点所代表的分类序列所需的比较次数等于该外结点所在的级数-1；,则，根据和的分析，有： n!2t(n) 化简： 当n1时，有n!n(n-1)(n-2)( )(n/2)n/2 当n4时，有 t(n)(n/2)log(n/2)(n/4)logn 故，任何以比较为基础的分类算法的最坏情况的时间下界为： (nlogn),2.快速分类 快速分类是一种基于划分的分类方法。 划分：在待分类集合a中选取某元素t，按照与t的大小关系重新整理a中元素，使得整理后t被置于序列的某位置上，而在t以前出现的元素均小于等于t，在t以后的元素均大于等于t。这一元素的整理过程称为划分（partitioning）。 划分元素：元素t被称为划分元素。 快速分类：这种通过对待排序集合反复划分达到分类目的算法称为快速分类算法。,1）算法描述 算法3.6 划分过程（partition）算法描述,procedure partition(m,p) /用a(m)划分集合a(m:p-1) integer m,p,i; global a(m:p-1) va(m);im /a(m)是划分元素/ loop loop ii+1 until a(i)v repeat / i由左向右移/ loop pp-1 until a(p)v repeat /p由右向左移/ if ip then call interchange(a(i),a(p) else exit endif repeat a(m)a(p)； a(p)v /划分元素在位置p/ end partition,a(p)被定义，但为一限界值，不包含在实际的分类区间内。,p,i,v,v,算法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 pq then jq+1 /进入时，a(j)定义了划分区间p,q的上界，首次调用时j=n+1 call partition(p,j) /出口时，j带出此次划分后划分元素所在的下标位置/ call quicksort(p,j-1) /对前一子集合递归调用 call quicksort(j+1,q) /对后一子集合递归调用 endif end quicksort,2）快速分类算法时间分析 统计的对象：元素的比较次数partition过程，记为：c(n) 两点假设 参加分类的n个元素各不相同 partition中的划分元素v是随机选取的（针对平均情况的分析） 随机选取划分元素： 在划分区间m,p-1随机生成某一坐标：irandom(m, p-1)； 调换a(m)与a(i)：va(i); a(i) a(m); im 作用：将随机指定的划分元素的值调换到a(m)位置。算法主体 不变。之后，仍从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（每次选取的划分元素刚好是当前集合中最小或最大者）,最坏情况分析 记最坏情况下的元素比较次数是cw(n)； partition一次调用中的元素比较数是p-m+1，若一级递归调用上处理的元素总数为r，则 partition的比较总数为o(r)。 最坏情况下（第i次调用partition所得的划分元素恰好是第i小元素），每级递归调用的元素总数仅比上一级少1，故cw(n)是r由n到2的累加和。 即：cw(n)= = (n2),平均情况分析 平均情况是指集合中的元素以任意顺序排列，且任选元素作为划分元素进行划分和分类，在这些所有可能的情况下，算法执行性能的平均值。 设调用partition(m,p)时，所选取划分元素v恰好是a(m:p-1)中的第i小元素（1ip-m）的概率相等。则经过一次划分，所留下的待分类的两个子文件恰好是a(m:j-1)和a(j+1:p-1)的概率是：1/(p-m), mjp。 记平均情况下的元素比较次数是ca(n)；则有， 其中，n+1是partition第一次调用时所需的元素比较次数。 ca(0) = ca(1) = 0,化简上式可得： ca(n)/(n+1) = ca(n-1)/n + 2/(n+1) = ca(n-2)/(n-1) + 2/n + 2/(n+1) = ca(n-3)/(n-2)+2/(n-1)+2/n+2/(n+1) = ca(1)/2+ 由于 所以得，ca(n)2(n+1)loge(n+1) = (nlogn),最坏情况下，递归的最大深度为n-1. 故，需要栈空间：o(n) 改进： 使用一个迭代模型可以将栈空间总量减至： o(logn),3）快速分类算法空间分析,4）一个改进了的快速分类迭代算法模型,处理策略：每次在partition将文件a(p:q)分成两个文件a(p:j-1)和a(j+1,q)后，先对其中较小的子文件进行分类。当小的子文件分类完成后，再对大的子文件进行分类。 栈：需要一个栈空间保存目前暂不分类的较大子文件。并在较小子文件分类完成后，从栈中退出最新的较大子文件进行下一步分类。,算法3.8 quicksort2(p,q) integer stack(1:max),top /max=2 global a(1:n);local integer j top0 loop while pq do jq+1 call partition(p,j); if j p q j /先对较小的子文件分类，并将规模较大的子文件入栈 then stack(top+1)j+1; stack(top+2)q; qj-1 else stack(top+1)p; stack(top+2)j-1; pj+1 endif toptop+2 /调整栈顶指针 repeat if top=0 then return endif /如果栈为空，算法结束 qstack(top);pstack(top-1); toptop-2 /从栈中退出先前保存的较大的子文件 repeat end quicksort2,算法quicksort2的最大空间是o(logn) 推导： 设算法所需的最大栈空间是s(n)，则有,1）经典的插入分类算法 经典的插入分类算法是通过对当前待插入的元素左侧的已排序数组进行遍历来查找插入位置的（回顾insertionsort算法）。 2）改进的插入分类算法 采用二分检索的原理，在待插入的元素左侧的已排序数组中查找插入位置。即， 在插入第i个元素时，对前面的0i-1元素进行折半，先跟它们的中间元素比，如果小，则对前半再进行折半，否则对后半进行折半，直到low high，然后把第i个元素前与目标位置之间的所有元素后移，再把第i个元素放在目标位置上。 （算法略）,3. 改进的插入分类算法,3.5 选择问题,1. 问题描述 在n个元素的表a(1:n)中找第k小元素，1kn。注：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小元素；否则， 若kj，则a(1:n)中的第k小元素将出现在a(j+1:n)中,第k小元素在a(j+1:n)中， 但是a(j+1:n)中的第k-j小元素,a(j)即是第k小元素,第k小元素在a(1:j-1)中, 且是a(1:j-1)中的第k小元素,j+1:新的起点,情况1：,情况2：,情况3：,3. 利用partition实现的选择算法,算法3.9 找第k小元素 procedure select(a,n,k) /在数组a(1:n)中找第k小元素，并将之放在a(k)中。/ integer n,k,m,r,j; m1;r n+1;a(n+1) + /a(n+1)被定义，并置为一大值，用于限界/ loop /在进入循环时，1mkrn+1 / j r /将剩余元素的最大下标加1后置给j / call partition(m.j) /返回j,它使得a(j)是第j小的值/ case :k=j: return :kj, j+1是新的下界/ endcase repeat end select,4. select算法分析 两点假设 a中的元素互异 随机选取划分元素，且选择a中任一元素作为划分元 素的概率相同 分析 每次调用partition（m,j),所需的元素比较次数是 (j-m+1)。 在执行一次partition后，或者找到第k小元素，或者将 在缩小的子集(a(m,k-1)或a(k+1,j)中继续查找。缩小 的子集的元素数比上一次划分的元素数至少少1。,1) 最坏情况 select的最坏情况时间是(n2) 最坏情况下的特例： 输入a恰好使对partition的第i次调用选用的划分元素是第i小元素，而k=n。 此时，（区间下界）m随着partition的每一次调用而仅增加1，j保持不变。 partition最终需要调用n次。 则,n次调用的时间总量是,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，1in。 则，存在正常数c，c0,有， n2 且有， n2,划分元素ik,将在i的后半部分求解,划分元素ik,将在i的前半部分求解,令cr(1)。利用数学归纳法证明，对所有n2，有r(n)4cn. 当n=2时，由上式得：, 假设对所有的n, 2nm，有r(n)4cn 当n = m时，有， 由于r(n)是n的非降函数，故当m为偶数而k=m/2，或当m为奇数而k=(m+1)/2时， 取得极大值。因此， 若m为偶数，则 若m为奇数，则 由于ta(n)r(n)，所以ta(n)4cn。 故，ta(n)=(n),5. 最坏情况是(n)的选择算法,1）采用两次取中间值的规则精心选取划分元素 目标：精心选择划分元素，避免随机选取可能出现的极端情况。 步骤：分三步 首先，将参加划分的n个元素分成 组，每组有r个元素(r1)。（多余的 个元素忽略不计） 然后，对这 组每组的r个元素进行分类并找出其中间元素mi,1i ，共得 个中间值一次取中。 之后，对这 个中间值分类，再找出其中间值mm。 将mm作为划分元素执行划分二次取中。,例：设 n=35, r=7。,分为n/r = 5个元素组： b1，b2，b3，b4，b5； 每组有7个元素。 b1-b5按照各组的mi的非降次 序排列。 mm = mi的中间值，1i5 由图所示有：,r个元素的中间值是第 小元素；,至少有 个mi小于或等于mm；,也至少有 个mi大于或等于mm。,故，至少有 个元素小于或等于mm。,同理，也至少有 个元素大于或等于mm。,以r=5为例。使用两次取中间值规则来选择划分元素v(即mm)，可得到， 至少有 个元素小于或等于选择元素v 且至多有 个元素大于等于v,同理， 至少有 个元素大于或等于选择元素v 且至多有 个元素小于等于v,故， 这样的v可较好地划分a中的n个元素：比足够多的元素大，也比足够多的元素小，不论落在那个区域，总可以在下一步查找前舍去足够多的元素，而在剩下的“较小”范围内继续查找。,2）算法描述 算法3.10 使用二次取中规则的选择算法的说明性描述 procedure select2(a,k,n) /在集合a中找第k小元素 若nr，则采用插入排序法直接对a分类并返回第k小元素。否则 把a分成大小为r的 个子集合，忽略多余的元素 设m=m1,m2,m 是 子集合的中间值集合 vselect2(m, , ) jpartition(a，v) case :k=j: return(v) :kj: 设s是a(1:j-1)中元素的集合; return(select2(s,k,j-1) :else: 设r是a(j+1:n)中元素的集合; return(select2(r,k-j,n-j) endcase end select2,3) 算法分析 记t(n)是select2所需的最坏情况时间 对特定的r分析select2：选取r=5。 假定a中的元素各不相同，则有 若nr，则采用插入法直接对a分类并返回第k小元素 (1) 把a分成大小为r的 个子集合，忽略多余的元素 (n) 设m=m1,m2,mr 是 子集合的中间值集合 (n) vselect2(m, , ) t(n/5) jpartition(a，v) (n) case t(3n/4),当n24 :k=j: return(v) :kj: 设s是a(1:j-1)中元素的集合; return(select2(s,k,j-1) :else: 设r是a(j+1:n)中元素的集合; return(select2(r,k-j,n-j) endcase end select2,将个数固定的r个元素的排序时间视为常数时间,注，由于r为定值，所以这里视对r个元素的直接排序的时间为“定值”o(1)。 故有， cn n 24, t(n) t(n/5)+t(3n/4)+cn n24 用归纳法可证： 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.6n 不再是线性关系。故有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。 则 当n90时，|s|和|r|都至多为 基于上述分析，有新的递推式：,相等元素的一半,c1n n90 t(n) t(n/9)+t(63n/72)+c1n n90 用归纳法可证： t(n)72c1n 即，t(n) = (n),算法中需要解决的两个问题 1) 如何求子集合的中间值？ 当r较小时，采用insertionsort(a,i,j)直接对每组的r个元素分类，在分类好的序列中，中间元素即为中间下标位置所对应的元素。 2) 如何保存 个子集合的中间值？ 在各组找到中间元素后，将其调整到数组a的前部，按子集合的顺序关系连续保存。从而可方便用递归调用的方式对这些中间值进行排序并找出中间值的中间值（即，二次取中）。,4）select2的实现,算法3.11 select2算法的实现 procedure sel(a,m,p,k) /返回一个i，使得im,p，且a(i)是a(m:p)中第k小元素，r是一个全程变量，其取值为大于1的整数 global r; integer n,i,j loop if p-m+1r then call insertionsort(a,m,p); return (m+k-1); endif np-m+1 /元素数/ for i1 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 jsel(a,m,m+ -1, )/mm/ call interchange (a(m),a(j) /产生划分元素，将之调整到第一个元素/ jp+1 call partition(m,j) case :j-m+1=k: return(j) :j-