假设有递推关系式 \(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 的指正)
如有不足之处,恳请斧正。
轻喷