假设有递推关系式 \(T(n) = aT(\frac n b )+ f(n)\)， 其中 \(T(n)\) 为问题规模， \(a\) 为递推的子问题的数量，\(\frac n b\) 为每个子问题的规模（假设每个字问题规模基本一样），\(f(n)\) 为递推以外进行的计算工作。\(a \geq 1,b>1\) 且为常数，\(f(n)\) 为函数，\(T(n)\) 为非负整数。则有以下结果（分类讨论）
-
若 \(f(n) = O(n^{\log_b a-\varepsilon})\) ，\(\varepsilon > 0\) ，那么 \(T(n) = \Theta(n^{log_b a})\)。
-
若 \(f(n) = \Theta(n^{\log_b a})\) ，\(\varepsilon > 0\) ，那么 \(T(n) = \Theta(n^{log_b a}\log n)\)
-
若 \(f(n) = \Omega(n^{\log_b a+\varepsilon})\) ，\(\varepsilon > 0\) ，且对于某个常数 \(c < 1\) 和所有充分大的 \(n\)，有 \(af(\frac n b) \leq cf(n)\) ，那么 \(T(n) = \Theta(f(n))\)
人话翻译
-
找出 \(a, b\)，计算 \(\log _b a\)。
-
找到 \(f(n)\) ， 找出它的次数 \(k\)。
-
比较 \(\log_b a\) 与 \(k\) 。
-
若 \(\log_b a > k\)，则时间主要消耗在递归上，\(T(n) = \Theta(n^{log_b a})\)。
-
若 \(\log_b a = k\)，则时间在递归和递归外的计算上消耗相等，\(T(n) = \Theta(n^{log_b a}\log n)\)。
-
若 \(\log_b a < k\)，则时间主要消耗在递归之外的计算上，\(T(n) = \Theta(f(n))\)。
-
当 \(f(n) = \Theta (n^{\log_b a}\log^kn)\)，其中 \(k \geq 1\) 且为一个常数，则有 \(T(n) = \Theta (n^{\log_b a}\log^{k+1}n)\)
（感谢 @Estelle_N 的补充）
实践一下
-
\(a = 2, b = 2, \log_2 2 = 1, k = 1.\log_b a = k\)，适用于主定理第二种情况，\(T(n) = \Theta(n^{log_b a}\log n) = \Theta(n\log n)\)。
-
\(a = 1, b = 2, \log_2 1 = 0, k = 1.\log_b a < k\)，适用于主定理第三种情况，\(T(n) = \Theta(f(n)) = \Theta(n)\)。
-
\(a = 1, b = 2, \log_2 1 = 0, k = 0.\log_b a = k\)，适用于主定理第二种情况，\(T(n) = \Theta(n^{log_b a}\log n) = \Theta(\log n)\)。
-
\(a = 2, b = 2, \log_2 2 = 1, k = 1.5.\log_b a < k\)，适用于主定理第三种情况，\(T(n) = \Theta(f(n)) = \Theta(n\sqrt n)\)。
还有一点
- $T(n) = 2^n T(\frac n 2) + n^n $
此处不满足主定理，\(a\) 不是常数
- \(T(n) = 16T(\frac n 4) + n\)
\(a = 16, b = 4, f(n) = n, \log_b a = 2, 2 > 1\)，适用于主定理第一种情况，\(T(n) = \Theta(n^2)\)。
某算法的计算时间表示为递推关系式 \(T(n) = T(n - 1) + n\)（\(n \in N^*\) ）及 \(T(0)=1\)，则该算法的时间复杂度为（\({\color{green}D}\)）。
A. \(O(\log n)\)
B. $O(n\log n) $
C. \(O(n)\)
D. \(O(n^2)\)
解析：此处不满足主定理
$ \therefore n + (n - 1) + (n - 2) + ... +1 = \sum\limits_{i = 1}^n i = \frac{(1+n)n}2 $
取最高项次数，复杂度为 \(O(n^2)\)。
若某算法的计算时间表示为递推关系式：
\(T(N) = 2T(\dfrac{N}{2}) + N \log N\)
\(T(1) = 1\)
则该算法的时间复杂度为（\({\color{green}C}\)）。
A.\(O(N)\)
B.\(O(N \log N)\)
C.\(O(N \log^2 N)\)
D.\(O(N^2)\)
解：
\(\log_ba = 1\)。当 \(k = 1\) 时，
\(\begin{aligned} f(N) &= \Theta (N^{\log_b a}\log^kN)\\ &=\Theta(N\log N) \end{aligned}\)
故
\(\begin{aligned} T(n) &= \Theta (n^{\log_b a}\log^{k+1}n)\\ &= \Theta(N^{1}\log^{1 + 1} N)\\&=\Theta(N\log^2 N) \end{aligned}\)
（感谢 @5k_sync_closer 的指正）
如有不足之处，恳请斧正。
轻喷