「算法」主定理

主定理

在演算法分析中，主定理提供了用渐近符号\(\Theta\) 表示许多由分治法得到的递推关系式的方法。

假设有递推关系式

\[ T(n)=aT(\frac{n}{b})+f(n) \]

那么有

\[ T(n)=\begin{cases} \Theta(f(n)) & f(n)=\Omega(n^{\log_b{a+\epsilon}})\ \&\&\ af(\frac{n}{b}) \leq f(n)\\ \Theta(n^{\log_ba}\log n) & f(n)=\Theta(n^{\log_b{a}})\\ \Theta(n^{\log_ba}) & f(n)=O(n^{\log_b{a-\epsilon}}) \end{cases} \]

其中 \(af(\frac{n}{b}) \leq f(n)\) 被称为正则条件，要求渐进意义上每一层的时间复杂度不大于上一层

可以发现决定 \(T(n)\) 形式的关键是 \(f(n)\) 与 \(n^{\log_b{a}}\) 之间的关系。 其中 \(n^{\log_b{a}}=a^{\log_bn}\) 也就是递推最后一层的节点个数。

那么可以形象化的理解：主定理的形式取决于层内复杂度和递推扩展复杂度中哪个作为主要影响因素

简化主定理

\[ T(n)=aT(\frac{n}{b})+n^k \]

对于这样的递推式，主定理可以简化为

\[ T(n)=\begin{cases} \Theta(n^k) & k>\log_ba\ \&\&\ af(\frac{n}{b}) \leq f(n)\\ \Theta(n^k\log n) & k=\log_ba\\ \Theta(n^{\log_ba}) & k<\log_ba \end{cases} \]

扩展主定理

考虑如下情形

\[ T(n)=2T(\frac{n}{2})+n\log n \]

\(f(n)=n\log n\) 落在 \(\Theta(n\log_b a)\) 和 \(\Omega(n\log_b{a+\epsilon})\) 之间（大了但没完全大），此时无法使用主定理进行处理，考虑扩展形式

\[ T(n)=\begin{cases} \Theta(f(n)) & f(n)=\Omega(n^{\log_b{a+\epsilon}})\ \&\&\ af(\frac{n}{b}) \leq f(n)\\ \Theta(n^{\log_ba}\log^{k+1} n) & f(n)=\Theta(n^{\log_b{a}}\log^kn)\\ \Theta(n^{\log_ba}) & f(n)=O(n^{\log_b{a-\epsilon}}) \end{cases} \]

增加了对 \(f(n)\) 中带有 \(\log^k n\) 的表达式的支持