004 [算法] 分区方法的时间复杂性分析

最编程 2024-05-21 14:54:09

...

最简单的应用分治策略的算法是归并排序，下面我们先给出归并排序的伪代码：

MERGE(A,p,q,r)
    n1=q-p+1
    n2=r-q
    //let L[1..n1+1] and R[1..n2+1] be new arrays
    for i=1 to n1
        L[i]=A[p+i-1]
    for j=1 to n2
        R[j]=A[q+j]
    L[n1+1]=∞
    R[n2+1]=∞
    i=1
    j=1
    for k=p to r
        if L[i]<=R[j]
            A[k]=L[i]
            i=i+1
        else
            A[k]=R[j]
            j=j+1
            
MERGE_SORT(A,p,r)
    if p<r
        q=(p+r)/2
        MERGE_SORT(A,p,q)
        MERGE_SORT(A,q+1,r)
        MERGE(A,p,q,r)

从上述伪代码我们可知，整段程序无非做了这么几件事情：

如果已经分解到最小颗粒n=1，那么直接返回即可，此时的时间复杂度????(1)
如果还不是最小颗粒，那么作折半分解，也即分解为L[1..n1+1]和R[1..n2+1]后进一步递归，此时的时间复杂度为2T(n/2)；其中这里忽略了分解本身的耗时，仅统计了处理分解后排序耗时
针对分解后的结果作一次归并，归并过程能够在线性时间内返回，所以此时的时间复杂度为????(n)

综上我们可知，归并排序的时间复杂度为：
$T(n)= \begin{cases} ????(1),\quad若n =1 \\ 2T(n/2)+????(n),\quad若n>1 \end{cases}$

教科书上告诉我们，归并排序的时间复杂度T(n)=????(nlgn)，那么它是怎么样计算出来的呢？下面给出几种解递归式的方法。

代换法

当我们有一定编程经验之后，其实对于算法的时间复杂度分析会有一定的直觉，而且随着经验的增长这种直觉的准确性也会越来越高。所以我们不妨先假设直觉是对的，然后对其进行验证即可，这就是假设验证法的基本思想：先猜答案，再给出验证。

先来个示例：
$T(n)=4T(\frac{n}{2})+n\tag{1}$

针对这样的一个递归式，如何求其时间复杂度？

先一步，我们先猜测，猜测(1)式的时间复杂度为????( $n^2$ )。

第二步，我们验证假设。如果我们的猜测是对的，那么根据上一讲的内容，针对(1)式我们就马上有如下的结论：
$T(k) \leq ck^2, \quad k \lt n\tag{2}$
于是我们对(1)式进行如下论证：
$\begin{align} T(n) & =4T(\frac{n}{2})+n\\ & \leq 4c*(n/2)^2+n\\ & = cn^2+n\\ & = cn^2-(-n)\tag{3} \end{align}$
好了，现在尴尬的事情出来了，要证明上式的最终结果小于 $cn^2$ ，就必须要求(-n)大于0，很显然这是不可能的。

难道我们的假设出了问题，直觉不准了？不应该呀……

问题出在(2)式上面，我们只考虑了高阶项，却忽略了低阶项对结果的影响，所以我们对(2)式进行改造，应是如下的结论：
$T(k) \leq c_1k^2-c_2k,\quad k \lt n\tag{4}$
我们应用(4)式再对(1)式进行改写，得到如下结果：
$\begin{align} T(n) & =4T(\frac{n}{2})+n\\ & \leq 4[c_1*(n/2)^2-c_2*(n/2)]+n\\ & = c_1n^2-2c_2n+n\\ & = c_1n^2-c_2n-[(c_2-1)n]\tag{5}\\ & \leq c_1n^2-c_2n\\ \end{align}$

很明显，为使(5)式中的 $(c_2-1)n$ 非负，只需要 $c_2\geq1$ 即可，显然这是可以的。

因此我们通过上述公式，严格论证了(1)式的时间复杂度T(n)=????( $n^2$ )针对所有的 $c_1\geq c_2$ 且 $c_2\geq1$ 有效。

递归树法

代换法的验证过程较为严谨，这里介绍一种我喜欢的方式，作树形图求解。一般的套路是先作图求解，而后用代换法进行验证，如果对自己比较自信的话，可以忽略验证

我们再来举个稍微复杂点的递归例子：
$T(n)=T(\frac{n}{4})+T(\frac{n}{2})+n^2\tag{6}$
如何求(6)式的时间复杂度？

话不多说，直接上图说话：

image-20200129190348513.png

是不是突然感觉原来如此简单？

另外最底层为什么是????(1)？因为归并算法最终分解之后都是单个元素，其时间复杂度自然是????(1)

我们继续求解，如下图所示：

image-20200129190440990.png

于是我们得到这样一个等比数列：
$\begin{align} T(n)&=T(\frac{n}{4})+T(\frac{n}{2})+n^2\\ &=n^2+\frac{5}{16}n^2+\frac{25}{256}n^2+...+\frac{5^k}{16^k}n^2+...\\ &=\frac{1-(\frac{5}{16})^k}{1-\frac{5}{16}}*n^2\\ &\leq 2n^2\\ &=????(n^2)=????(n^2) \end{align}$

于是问题得以求解，为求稳妥可应用代换法进行验证，此处略过。

主定理法

最后介绍一种主定理法，其根本是递归树法的应用，它有诸多限制，只能应用于形如下式的递归式上：
$T(n)=aT(\frac{n}{b})+f(n),\quad a\geq1,b\gt1,f(n)渐近趋正 \tag{7}$

应用主定理，我们有三种情景：

当f(n)< $n^{log_ba}$ 时，T(n)=????( $n^{log_ba}$ )
当f(n)= $n^{log_ba}$ 时，T(n)=????( $n^{log_ba}*lg^{k+1}n$ )
当f(n)> $n^{log_ba}$ ，同时 $af(\frac{n}{b})\leq(1-????)+f(n)$ 时，T(n)=????(f(n))，原因是代价逐级递减之后，f(n)开始占主导地位

这里就不详细证明了，其实可以根据上述递归树法进行论证。其中， $n^{log_ba}$ 表示递归树中的叶节点个数，其中递归树的高度为 $log_bn$ 。

应用此主定理，我们立马可以得知(1)式符合情况1，其时间复杂度T(n)=????( $n^2$ )

所以，现在大家知道为什么归并排序的时间复杂度T(n)=????(nlgn)了吗？

上一篇：分区、动态程序设计、贪婪、回溯、分支定义

下一篇：分治法算法总结

004 [算法] 分区方法的时间复杂性分析

代换法

递归树法

主定理法

004 [算法] 分区方法的时间复杂性分析

算法复杂性分析（上）：分析算法运行时对时间和空间资源的消耗。