分治策略(二)


在分治策略(一)中,介绍了分治策略的算法思想及运行时间的递归表示。这一章,来看一下一个具体的相关算法,归并排序算法;最后我们会用递归树的方式分析归并排序运行时间。

算法分析

归并排序算法,实际上是将原问题分解成为两个子问题,分别求解两个子问题的解后,再合并子问题得到原问题的解。

根据上述描述及实现分治策略三个步骤,可以稍得到归并排序的一般步骤:
1.分解原问题为2个子问题;
2.求解子问题;
3.合并子问题,得到原问题的解;

还记得用递归方程给出分治策略类算法的运行时间吗?
T(n) = Θ(1) 当n<=c
T(n) = aT(n/b) + D(n) + C(n) 其他

那么a=b=2时,便能根据上面的式子得出归并排序算法的运行时间的递归表示:
T(n) = Θ(1) 当n = 1
T(n) = 2T(n/2) + D(n) + C(n) 其他

实际上,原问题的规模,并不能一定分成两个规模相等的子问题,严格来说,应该写成

T(n) =T(⌈n/2⌉) + T(⌊n/2⌋) + D(n) + C(n)

但为了简化分析,同时不影响递归式解的增长量级,假设n,即问题的规模是2的幂,这样每次分解问题,都能得到规模恰好为n/2点的子问题。

当n == 1时,算法运行时间为常量,记为Θ(1);
当n>1时:
分解:因为每次分解,仅仅需要确定中间位置,和当前问题规模无关,因此,常量时间完成,记为D(n)=Θ(1);
解决:排序两个子问题的解运行时间之和2T(n/2);
合并:合并两个已经排序好的子数组,最多Θ(n)时间可完成,所以记为C(n)=Θ(n)。(Θ(n)可以理解为关于n的一个线性函数)

这样,我们得到进一步简化的归并排序最坏运行时间的递归式:

T(n) = Θ(1) 当n = 1
T(n) = 2T(n/2) + Θ(n) 当n>1

利用递归树求解运行时间过程

通过主定理,求解算法最坏情况下的运行时间为Θ(nlgn);但这里不讨论主定理,我们用递归树直观的理解为什么归并排序最坏运行时间为Θ(nlgn)。

将上面的递归式重写:

T(n) = c 当n = 1
T(n) = 2T(n/2) + cn 当n>1

c表示求解规模为1的问题所需的时间,以及分解合并处理每个数组元素所需的时间。注意:求解规模为1的问题所需的时间与分解合并处理每个数组元素所需的时间,一般不可能相同,这里假设c为这两个时间的最大者,将得到运行时间的一个上界;假设c为这两个时间的最小者,将得到运行时间的一个下界;这两个界的最大阶都为nlgn,所以通过假设c,可以规避上面提到的情况;算法分析更加容易。

值得指出的是,在算法分析中,经常会在不影响最大项的前提下,做适当假设或者直接丢弃常数项和低阶项,来规避对结果影响不大的部分,简化分析过程。

构造递归树的过程,就是求解递归式的过程,构造一个递归树的过程如图:
5E08D7C2-7DB9-4634-BC0A-50B3A2E2FB2

递归树构建完成后,我们发现递归树有lgn+1层,高度为lgn,每层运行时间为cn,所以总的运行时间为cn*(lgn+1)=cnlgn + cn,记为Θ(nlgn)。

递归树求解其他代价

递归式不仅只用来可以表示运行时间,其他的资源代价计算也通常会用到递归式,比如空间复杂度。所以,这种用递归树的方式来求解递归式,具有普适性。

知识共享许可协议本作品采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。
本站文章除注明转载/出处外,均为本站原创或翻译,请务必在遵守许可协议的前提下转载。
发布时间:2018-09-12 18:09:36 阅读:871 标签:算法技术