主定理(Master Theorem)

article/2025/9/19 3:57:42

主定理是分析分治算法时间复杂度很重要的一个定理。

我们之前对于一个递归类的代码进行时间复杂度分析，一般会采用递归树的方式，下面我们先介绍一下递归树的方式，理解之后，再引入主定理的相关内容。

分治的介绍

分治算法总是将问题的规模不断的拆分，以归并排序为例。

假设 $T (n)$ 代表原问题的规模， $n$ 为输入数据的规模。

第一次拆分后，假设拆分成两份，规模就变成了 $\frac{n}{2}$ ，然后各自再递归调用归并排序，这部分时间复杂度为 $2T(\frac{n}{2})$ ，最后将这两个排好序的子数组进行合并，所需时间为 $\Theta(n)$ 。

$\Theta$ 为同阶， $\Omega$ 为下界， $O$ 为上界。

那么就可以得出：
$\left \{ \begin{aligned} & \Theta(1) \quad n=1 \\ & 2T(\frac{n}{2})+\Theta(n) \quad n>1 \end{aligned} \right.$

递归树

以 $T(n)=3T(\frac{n}{4})+\Theta(n^2)$ 为例：

在这里插入图片描述

总代价为:

$\begin{aligned} T(n) &=cn^2+\frac{3}{16}cn_2+(\frac{3}{16})^2cn^2+...+(\frac{3}{16})^{log_4^{n-1}}cn^2+\Theta(n^{log_4^3})\\ &=\sum_{i=0}^{log_4^{n-1}}(\frac{3}{16})^icn^2+\Theta(n^{log_4^3})\\ &<\sum_{i=0}^{\infty}(\frac{3}{16})^icn^2+\Theta(n^{log_4^3}) \quad \text{放缩}\\ &=\frac{1}{1-\frac{3}{16}}cn^2+\Theta(n^{log_4^3}) \\ &=\frac{16}{13}cn^2+\Theta(n^{log_4^3}) \quad \quad \Theta(n^{log_4^3})\text{低阶项}\\ &=O(n^2) \quad \text{上界} \end{aligned}$
同时我们知道，每一项都包含 $n^2$ ，并且系数都是正的，那么下界为 $T(n)=\Omega(n^2)$ 。

主定理

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

a: 被分解为a个子问题。

b: >1的整数，表示每次分治，问题规模都被缩小为之前的 $\frac{1}{b}$ 。

$f (n)$ : 渐进正函数，表示分解和合并的代价。

在这里插入图片描述

总代价为: $T(n)=\Theta(n^{log_b^a})+\sum_{j=0}^{log_b^{n-1}}a^jf(\frac{n}{b^j})$

设 $g(n)=\sum_{j=0}^{log_b^{n-1}}a^jf(\frac{n}{b^j})$ ， $\Theta(n^{log_b^a})$ 和之间 $f (n)$ 的大小关系决定了 $g (n)$ 的化简形式。

若 $\Theta(n^{log_b^a})>f(n)$ ，
$g(n)=O(n^{log_b^a})$
那么，
$\begin{aligned} T(n) &=\Theta(n^{log_b^a})+O(n^{log_b^a})\\ &=\Theta(n^{log_b^a})\quad (\text{同阶}) \end{aligned}$
若 $\Theta(n^{log_b^a})=f(n)$ ，
$g(n)=\Theta(n^{log_b^a}logn)$
那么，
$\begin{aligned} T(n) &=\Theta(n^{log_b^a})+\Theta(n^{log_b^a}logn)\\ &=\Theta(n^{log_b^a}logn)\quad (\text{同阶}) \end{aligned}$
若 $\Theta(n^{log_b^a})<f(n)$ ，
$g(n)=\Theta(f(n))$
那么，
$\begin{aligned} T(n) &=\Theta(n^{log_b^a})+\Theta(f(n))\\ &=\Theta(f(n)) \end{aligned}$

综上所述：
$\left \{ \begin{aligned} &\Theta(n^{log_b^a}) & \Theta(n^{log_b^a})>f(n)\\ &\Theta(n^{log_b^a}logn) & \Theta(n^{log_b^a})=f(n)\\ &\Theta(f(n)) & \Theta(n^{log_b^a})<f(n) \end{aligned} \right.$
举个例子：

$T(n)=T(\frac{2n}{3})+1$

$n^{log_b^a}=n^{log_\frac{3}{2}^1}=1$ 与 $f (n) = 1$ 相等，因此 $T(n)=\Theta(n^{log_b^a}logn)=\Theta(nlogn)$ 。
$T(n)=3T(\frac{n}{4})+n^2$

$n^{log_b^a}=n^{log_4^3}$ ， $f(n)=n^2$ ，因此 $T(n)=\Theta(n^2)$ ，和上面递归树推出来的一样。