算法-08-主定理

Master theorem（主定理）是一种用于解决以下形式的递推关系的工具：

其中：

• $n$ 是问题的规模
• $a \geq 1$ 和 $b > 1$ 是常数
• $f(n)$ 是一个函数，表示分解和合并子问题所需的时间

主定理给出了递推关系解的渐近界，具体取决于 $f(n)$ 相对于 $n^{\log_b a}$ 的增长速度。

主定理的三种情况

1. 若 $f(n) = O(n^{\log_b a - \epsilon})$，其中 $\epsilon > 0$，则 $T(n) = \Theta(n^{\log_b a})$。

直观解释：如果分解和合并子问题的时间增长得比 $n^{\log_b a}$ 慢，那么总时间就由叶子节点上的工作所主导，即 $T(n) = \Theta(n^{\log_b a})$。

2. 若 $f(n) = \Theta(n^{\log_b a} \log^k n)$，其中 $k \geq 0$，则 $T(n) = \Theta(n^{\log_b a} \log^{k+1} n)$。

直观解释：如果分解和合并子问题的时间与 $n^{\log_b a}$ 同阶，那么总时间就在递归树的每一层都是相同的，即 $T(n) = \Theta(n^{\log_b a} \log^{k+1} n)$。

3. 若 $f(n) = \Omega(n^{\log_b a + \epsilon})$，其中 $\epsilon > 0$，且对于某个常数 $c < 1$ 和所有足够大的 $n$ 有 $af(n/b) \leq cf(n)$，则 $T(n) = \Theta(f(n))$。

直观解释：如果分解和合并子问题的时间增长得比 $n^{\log_b a}$ 快，且满足 $af(n/b) \leq cf(n)$ 的条件（即分解后的子问题的总工作量比原问题少），那么总时间就由根节点上的工作所主导，即 $T(n) = \Theta(f(n))$。

主定理的应用

主定理可以用于分析许多基于分治策略的算法的时间复杂度，如归并排序、快速排序、Strassen矩阵乘法等。

以归并排序为例，其递推关系为：

对应于主定理的情况2，其中 $a=2$，$b=2$，$f(n)=\Theta(n)=\Theta(n^{\log_b a} \log^0 n)$。因此，归并排序的时间复杂度为 $T(n) = \Theta(n \log n)$。

主定理的局限性

主定理只适用于那些可以写成 $T(n) = aT(n/b) + f(n)$ 形式的递推关系，其中 $a \geq 1$，$b > 1$，且 $f(n)$ 是渐近正的。对于其他形式的递推关系，如 $T(n) = 2T(n/2) + n \log n$ 或 $T(n) = T(n-1) + T(n-2)$，主定理就不再适用。此外，主定理也不适用于那些子问题大小不均匀或子问题数量不固定的分治算法。

在这些情况下，需要使用其他方法来分析时间复杂度，如代入法、递归树法、均摊分析等。