递归时间复杂度分析-主定理分析
标签： 算法 复杂度分析
1. 主定理定义
以下是评估递归时间复杂度的主定理，例如有递归形式
\]
其中, \(a≥1\)和\(b≥1\), 均为常数, \(f(n)\)是一个确定的正函数。 在\(f(n)\)的三类情况下, 我们有\(T(n)\)的渐近估计式：
-
若对于某常数\(ε>0\), 有\(f(n) = O(n ^ {log_b a – ε} )\), 则\(T(n) = \Theta(n ^ {log_b a})\)
-
若\(f(n) = O(n ^ {log_b a})\), 则\(T(n) = O(n ^ {log_b a} *lgn)\)
-
若对某常数\(ε>0\), 有\(f(n)=\Omega(n ^{log_b a + ε})\), 且对常数\(c<1\) 与所有足够大的\(n\),有\(af(n/b)\le cf(n)\), 则\(T(n)=\Theta(f(n))\)。
2. 主定理使用方式
主定理可以理解为：
情况1, 若\(f(n) \lt n ^ {log_b a}\), 则复杂度为 $T(n)=\Theta(n ^ {log_b a}) \(;
情况2, 若\)f(n) = n ^ {log_b a}$, 则复杂度为 $T(n)=\Theta(n ^ {log_b a} * lg n) \(;
情况3, 若\)f(n) \gt n ^ {log_b a}$, 则复杂度为 $T(n)=\Theta(f(n)) $。
3. 主定理应用示例
（1）求\(T(n) = 9T(n/3) + n\)
其中\(a = 9\), \(b = 3\), \(f(n) = n\), 代入求解得 \(n ^{log_3 9} = n ^ 2\), 由于\(f(n) < n ^ 2\), 情况1成立，\(T(n) = \Theta(n ^ 2)\)
（2）求\(T(n) = T(2n/3) + 1\)
其中\(a = 1\), \(b = 3/2\), \(f(n) = 1\), 代入求解得 \(n ^{log_{3/2} 1} = n ^ 0 = 1\), 由于\(f(n) = 1\), 情况2成立，\(T(n) = \Theta(lg n)\)
（3）归并排序的复杂度分析
（二路）归并排序属于分治法，本质是先把数组分成两半，再做合并操作，其中合并操作复杂度为常数\(c\)，则可以看作
\]
其中\(a=2\), \(b = 2\),$ f(n) = c\(, 则根据主定理分析，\)n^{log_2 2} = n ^ 1 = 1 $, 属于情况2, 则归并排序的复杂度为
\]