主定理（Master Theorem）是一种常见于算法分析中的工具。它指出了如何解决与分治和递归有关算法的时间复杂度。
主定理
主定理的标准形式是分析以下递归式的实际复杂度：
\[T(n) = aT\left(\frac{n}{b}\right) + f(n), \]其中：
- \(a \geq 1\) 是递归调用的数量，表明问题被切割为几个子问题。
- \(b > 1\) 是每次递归将问题规模缩小的因子，表明问题子问题的规模。
- \(f(n)\) 是所有递归调用以外的额外工作量。
主定理的核心思想是比较递归的部分和非递归部分哪个增长得更快，从而决定算法的总体复杂度。根据 \(f(n)\) 的增长速度与 \(n^{\log_b a}\) 的比较，主定理分为以下三种情形：
-
\(f(n) \in O(n^{\log_b a - \epsilon})\)，某个 \(\epsilon > 0\)
此时递归部分主导增长，时间复杂度为 \(T(n) \in \Theta(n^{\log_b a})\)。 -
\(f(n) \in \Theta(n^{\log_b a})\)
此时递归部分与非递归部分增长相当，时间复杂度为 \(T(n) \in \Theta(n^{\log_b a} \log n)\)。 -
\(f(n) \in \Omega(n^{\log_b a + \epsilon})\)，某个 \(\epsilon > 0\) 且 \(a f\left(\frac{n}{b}\right) \leq c f(n)\)（即递归调用的贡献足够小）
此时非递归部分主导增长，时间复杂度为 \(T(n) \in \Theta(f(n))\)。
简单的理解
主定理的证明主要依赖于累加每一层递归所消耗的工作量。我们可以把递归的过程看作是一棵树，其中：
- 树的每一层表示一次递归调用。
- 每一层的总工作量由 \(a\) 个子问题的工作量 \(T(n/b)\) 和外部工作量 \(f(n)\) 构成。
对于总工作量，我们逐层分析：
树的结构
- 第 \(k\) 层的子问题规模为 \(\frac{n}{b^k}\)。
- 第 \(k\) 层有 \(a^k\) 个子问题，每个子问题需要的工作量为 \(f\left(\frac{n}{b^k}\right)\)。
总工作量
树的总工作量为所有层的工作量之和：
\[\text{Total Work} = \sum_{k=0}^{\log_b n} a^k f\left(\frac{n}{b^k}\right). \]通过数学上对该式的收敛性和增长性分析证明，最终可以得出上述主定理的三种情况：
- 若 \(f(n)\) 增长较慢（情况 1），则递归部分占主导。
- 若 \(f(n)\) 和递归增长相等（情况 2），需额外乘以 \(\log n\)。
- 若 \(f(n)\) 增长较快且满足平衡条件（情况 3），则非递归部分占主导。
实例
二分查找
递归式为：
\[T(n) = T\left(\frac{n}{2}\right) + O(1). \]这里：
- \(a = 1\)（一次递归调用），
- \(b = 2\)（问题规模缩小一半），
- \(f(n) = O(1)\)。
根据主定理：
\[\log_b a = \log_2 1 = 0. \]比较 \(f(n) = O(1)\) 和 \(n^0 = O(1)\)，属于情况 2，因此复杂度为 \(T(n) \in \Theta(\log n)\)。
归并排序
递归式为：
\[T(n) = 2T\left(\frac{n}{2}\right) + O(n). \]这里：
- \(a = 2\)，\(b = 2\)，\(f(n) = O(n)\)。
根据主定理：
\[\log_b a = \log_2 2 = 1. \]比较 \(f(n) = O(n)\) 和 \(n^1 = O(n)\)，属于情况 2，因此复杂度为 \(T(n) \in \Theta(n \log n)\)。
Strassen 矩阵乘法
递归式为：
\[T(n) = 7T\left(\frac{n}{2}\right) + O(n^2). \]这里：
- \(a = 7\)，\(b = 2\)，\(f(n) = O(n^2)\)。
根据主定理：
\[\log_b a = \log_2 7 \approx 2.81. \]比较 \(f(n) = O(n^2)\) 和 \(n^{2.81}\)，属于情况 1，因此复杂度为 \(T(n) \in \Theta(n^{2.81})\)。
主定理的应用
主定理的思想广泛应用于算法分析，在算法分析中有许多拓展：
- 扩展主定理：处理一些递归项的非对称性或 \(f(n)\) 的非多项式增长形式。
- 递归树法：直接可视化每层的工作量，适用于无法直接套用主定理的递归式。
- 代入法：通过假设形式化时间复杂度并验证其成立性来解决递归式。
主定理要求递归式严格符合标准形式，对于不符合形式的递归式（如非均匀分割），还需要其他方法分析。另外，主定理只指出了 \(f(n)\) 的一部分情况，若 \(f(n)\) 的条件复杂（如渐进有界性），主定理在一些复杂问题中可能较难满足条件，还需要其他工具。
标签：用主,frac,log,递归,复杂度,工作量,定理 From： https://www.cnblogs.com/ofnoname/p/18598818