分治问题中递归函数时间复杂度浅析

Preface

在各类分治 (Divide-and-Conquer) 问题中, 我们经常使用递归函数来方便地进行子问题的处理和结果的合并. 典型的例子有归并排序 (merge sort) 和离散快速傅里叶变换 (Fast Fourier Transform)。对于这种递归函数算法的时间复杂度分析我们可以使用三种方法:代入法 (The substitution method) , 递归树法 (The recursion-tree method) 和使用大名鼎鼎的主定理 (The Master Theorem) 的主定理法 (The Master Method) .

在这里, 我们使用这样的方法表示一个递归函数, 例如:$T(n) = 2T(\lceil \frac{n}{2} \rceil) + n$

代入法(The substitution method)

所谓代入法其实就是猜一个答案，然后将这个答案代入递归函数的表达式中来验证我们的猜测是正确的，其实是用到了数学归纳的方法.

_e.g._ 求$T(n) = 2T(\lfloor \frac{n}{2} \rfloor) + n$的时间复杂度上界(upper bound).

我们首先猜想答案是$O(nlog_2 n)$, 所以我们需要证明$T(n) <= c n log_2 n$. 不妨假设这个结论已经对所有小于$n$的数成立,于是代入$T(\lfloor \frac{n}{2} \rfloor)$

得

显然当$c>=1$时可以说明我们的假设是正确的

为了严格证明我们当然还需要注意两个方面:第一个是达到边界时的情况(也就是递归树的叶节点);还有一个就是归纳的起始条件,也就是说，为了归纳证明，我们需要另外证明$n$在小于某一个数时我们的假设是成立的。但是为了方便起见，我们可以不用处理上述因素。

我们需要猜测一个答案来开始我们的代入法， 但是很多时候我们可能并不能第一下就猜出正解，我们可以先猜一个比较松的界，然后逐步收敛得到我们想要的答案。

同时算法导论上还讲述了一个比较精巧的方法, 当我们猜测出来的答案并不足够强以证明不等式，我们可以在猜测的不等式中减去低阶项(lower-order term)后再代入。

例如算法导论中给出的例子$T(n) = T(\lfloor \frac{n}{2} \rfloor)+T(\lceil \frac{n}{2} \rceil)+1$

如果我们猜测$T(n)<=cn$,发现带入结果是$T(n)<=cn+1$，不足以证明我们的猜想

这时我们减去一个低阶项$T(n)<= cn-d$再次代入,得$T(n)<=cn-2d+1$, 只要$d>=1$,$T(n)<=cn-d$就成立

递归树法(The recursion-tree method)

咕

主定理法(The master method)

主定理法是为了求出下述通式的递归式的时间复杂度的

$a,b$均为大于等于$1$的常数，$f(n)$是一个渐进正函数(asymptotically positive function)

这里的$\frac{n}{b}$既可以指上取整也可以指下取整

主定理法当然是依据下面这个主定理来的:

1. If $f(n)=O(n^{\log_ba-\epsilon})$ for some constant $\epsilon>0$,then $T(n)=\Theta(n^{\log_ba})$.

2. If $f(n)=\Theta(n^{\log_ba})$,then $T(n)=\Theta(n^{\log_ba}\lg n)$.

3. If $f(n)=\Omega(n^{\log_ba+\epsilon})$ for some constant $\epsilon>0$, and if $af(n/b)\le cf(n)$ for some constant $c<1$ and all sufficiently large $n$,then $T(n)=\Theta(f(n))$.

Introduction To Algorithms,Page 94, 3rd edition

举几个例子:

递归建堆 $T(n) = T(2n/3) + 1$

$a=1, b=\frac{3}{2}, log_b^a = 0, n^{log_b^a} = 1 = f(n)$

所以 $T(n) = \Theta(logn)$

归并排序 $T(n)=2T(n/2)+ \Theta(n)$

$a=2, b=2, n^{log_b^a} = n$

所以 $T(n)= \Theta(nlogn)$

References

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to algorithms. MIT press., http://thuvien.thanglong.edu.vn:8081/dspace/bitstream/DHTL_123456789/3760/2/introduction-to-algorithms-3rd-edition.pdf