貴方が私の Master Theorem か
传说，在日本冬木市，每隔数十年，会出现能实现其持有者所有愿望的宝物「圣杯」。七名御主 (マスター, Master ) 与七名从者 (サーヴァント, Servant) 签订契约，为了争夺圣杯而参与秘密的「圣杯战争」。
能获得圣杯的只有一组，这七组人马各自为了成为最后的那一组而互相残杀。为了赢下圣杯战争，男主角卫宫士郎与他的从者 Saber 必须解出某种基于分治的递归式算法 (形如 \(T(n)=aT(\frac{n}{b})+f(n)\)) 的时间复杂度。
阴差阳错之下，士郎得到了宝具「御主之律法」(マスターテオリム, Master Theorem )，但面对斐波那契数列时还是束手无策。他希望你能帮助他与 Saber 解决这个问题。
Master Theorem
主定理适用于求解如下递归式算法的时间复杂度： \[ T(n)=aT(\frac{n}{b})+\Theta(n^d) \]
- \(n\) 是问题规模；
- \(a\) 是原问题的子问题个数。
- \(b\) 是由原问题到子问题所削减的规模；因此子问题的规模为 \(\frac{n}{b}\)。
- \(\Theta(n^d)\) (有时写成 \(f(n)\)) 是将原问题分解为子问题与将子问题的解合并为原问题的解所需的时间。
主定理指出，对于此类型的递归式算法，其时间复杂度为： \[ T(n)= \begin{cases} \Theta(n^d) \ \ \ \ \ \ \ \ \ \ \ \ \ {\rm{if}} \ d>\log_b a \\ \Theta(n^d\log n) \ \ \ \ {\rm{if}} \ d=\log_ba \\ \Theta(n^{\log_b a}) \ \ \ \ \ \ \ \ {\rm{if}} \ d<\log_ba \end{cases} \]
Where does it come from?
将递归式 \(T(n)=aT(\frac{n}{b})+O(n^d)\) 展开：
| Level | Problem size | Problem # | Work (current level) |
|---|---|---|---|
| 0 | \(n\) | 1 | \(\Theta(n^d)\) |
| 1 | \(n/b\) | \(a\) | \(a\Theta((n/b)^d)=\Theta(n^d)\frac{a}{b^d}\) |
| 2 | \(n/b^2\) | \(a^2\) | \(a^2\Theta((n/b^2)^d)=\Theta(n^d)(\frac{a}{b^d})^2\) |
| ... | ... | ... | ... |
| \(k\) | \(n/b^k\) | \(a^k\) | \(\Theta(n^d)(\frac{a}{b^d})^k\) |
| ... | ... | ... | ... |
| \(\log_bn\) | \(n/b^{\log_bn}\) | \(a^{\log_bn}\) | \(\Theta(1)a^{\log_bn}\) |
求 total work 就是对每一层的 work 求和；可以发现这是一个等比数列求和问题： \[ {\rm{Total \ work}}=T(n)=\sum_{0}^{\log_bn}\Theta(n^d)(\frac{a}{b^d})^i \] 首先提出一个引理：任意一个等比数列之和不会大于其最大项的常数倍。
例如，对于 \(q<1\) 的等比数列 \(\{a_n\}\)，显然 \(a_1\) 是其最大项。那么 \(\{a_n\}\) 的和 \(S=\frac{a_1(1-q^n)}{1-q}\leq O(a_1)\)。很好证明：由于 \(q<1\)，\(\lim_{n\to\infty}\frac{1-q^n}{1-q}=\frac{1}{1-q}=O(1)\) (与 \(n\) 无关)。
根据该引理，\(\Theta({\rm{Total \ work}})\) 能被其最大项的时间复杂度表示，即 \(O(a_1) \ (q<1)\) 或 \(O(a_n) \ (q>1)\)。
至此，我们能够(不严谨地)对主定理进行证明：
- 当 \(q=a/b^d<1\) 即 \(d>\log_ba\) 时，\(\Theta(\rm{Total \ work})\) 被首项决定，即 \(T(n)=\Theta(n^d)\)。在该情况下，将原问题分解为子问题与合并子问题解所需的时间是 dominant term。
- 当 \(q=a/b^d>1\) 即 \(d<\log_ba\) 时，\(\Theta(\rm{Total \ work})\) 被末项决定，即 \(T(n)=\Theta(a^{\log_bn})=\Theta(n^{\log_b a})\)。在该情况下，解决子问题所需的时间是 dominant term。
- 当 \(q=a/b^d=1\) 即 \(d=\log_ba\) 时，要求 \(\Theta(\rm{Total \ work})\) 必须对数列求和。注意到这一数列的 \(q=1\)，这意味着每一项都相同，因此 \(T(n)=(\log_bn+1)\Theta(n^d)=\Theta(n^d\log_bn)\)。在该情况下，将原问题分解为子问题+合并子问题解所需的时间与解决子问题所需的时间在渐进意义上具有同等重要性。
Examples
- 经典的 binary search：\(T(n)=T(n/2)+\Theta(1)\)。
- \(a=1, b=2, d=\log_n1=0\)。由于 \(\log_ba=d=0\)，适用于 case 3: \(T(n)=\Theta(\log n)\)。
- 归并排序 merge sort：\(T(n)=2T(n/2)+\Theta(n)\)。
- \(a=b=2, d=\log_n n=1\)。由于 \(\log_ba=d=1\)，适用于 case 3: \(T(n)=\Theta(n\log n)\)。
- 二叉树遍历：\(T(n)=2T(n/2)+\Theta(1)\)。
- \(a=b=2, d=\log_n1=0\)。由于 \(\log_ba>d\)，适用于 case 2: \(T(n)=\Theta(n)\)。
Fibonacci Sequence
并不是所有递归算法的时间复杂度都能用主定理进行求解。
1 | int fib(int n) { |
这是求斐波那契数列第 \(n\) 项的朴素算法。该算法时间复杂度的递归表示为： \[ T(n)=T(n-1)+T(n-2) \] 注意到该式并不符合形如 \(T(n)=aT(n/b)+\Theta(n^d)\) 的分治形式，因此不能用主定理进行求解。借此机会，我们顺便研究一下如何求解以上算法的时间复杂度 \(T(n)\)。首先，我们提出斐波那契数列的通项公式：
General Formula
简单介绍一下该通项公式的推导。首先将斐波那契数列的递归表达式 \(F_n=F_{n-1}+F_{n-2}\) 写成矩阵形式： \[ \begin{bmatrix} F_n \\ F_{n-1} \\ \end{bmatrix}= \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} F_{n-1} \\ F_{n-2} \end{bmatrix} \] 展开后得： \[ \begin{bmatrix} F_n \\ F_{n-1} \end{bmatrix}= \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} F_{n-1} \\ F_{n-2} \end{bmatrix}= \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^2 \begin{bmatrix} F_{n-2} \\ F_{n-3} \end{bmatrix}=...= \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^{n-2} \begin{bmatrix} F_2 \\ F_1 \end{bmatrix}=A^{n-2} \begin{bmatrix} 1\\ 1 \end{bmatrix} \] 至此问题转化为求矩阵 \(A\) 的 \(n-2\) 次方。应用 \(\det(A-\lambda I)=0\) 求出 \(A\) 的两个 eigenvalues： \[ \lambda_1=\frac{1-\sqrt{5}}{2}, \lambda_2=\frac{1+\sqrt{5}}{2} \] 接下来对 \(A\) 进行 eigen decomposition: \(A=Q\Lambda Q^{-1}\)，求出 \(Q\) 与 \(\Lambda\) 分别为： \[ Q=\begin{bmatrix} \lambda_1&\lambda_2 \\ 1&1 \end{bmatrix}, \Lambda= \begin{bmatrix} \lambda_1&0 \\ 0&\lambda_2 \end{bmatrix} \] 对 \(A\) 进行 eigen decomposition 后再进行乘方运算： \[ \begin{aligned} \begin{bmatrix} F_n\\ F_{n-1} \end{bmatrix}&=A^{n-2} \begin{bmatrix} 1\\1 \end{bmatrix}\\&=Q\Lambda^{n-2}Q^{-1} \begin{bmatrix} 1\\1 \end{bmatrix}\\&= \begin{bmatrix} \lambda_1&\lambda_2\\ 1&1 \end{bmatrix} \begin{bmatrix} \lambda_1&0\\ 0&\lambda_2 \end{bmatrix}^{n-2} \begin{bmatrix} \lambda_1&\lambda_2\\ 1&1 \end{bmatrix}^{-1} \begin{bmatrix} 1\\1 \end{bmatrix}\\&= \frac{1}{\lambda_1-\lambda_2} \begin{bmatrix} \lambda_1^n-\lambda_2^n\\ \lambda_1^{n-1}-\lambda_2^{n-1} \end{bmatrix} \end{aligned} \] 至此我们求出斐波那契数列 \(\{F_n\}\) 的通项公式： \[ F_n=\frac{\lambda_1^n-\lambda_2^n}{\lambda_1-\lambda_2}=\frac{1}{\sqrt{5}}[(\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n] \]
Time Complexity
注意到该算法时间复杂度的递归表示为 \(T(n)=T(n-1)+T(n-2)\)，其本质上是一个首项为 \(O(1)\) 的斐波那契数列；因此该算法的时间复杂度 \(T(n)\) 与 \(F_n\) 的增长率一致。
由此得出 \(T(n)\sim \Theta(F_n)\)，即 \(T(n)\sim \Theta(\frac{1}{\sqrt{5}}[(\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n])\)。观察到 \((\frac{1-\sqrt{5}}{2})^n\) 在 \(n\to\infty\) 的情况下趋近于 \(0\)，再忽略常数 \(1/\sqrt{5}\)，我们可以总结出：