主定理

Master Theorem | 主定理

定义 | Definition

主定理是用于求解形如 $T(n)=aT\left(\frac{n}{b}\right)+f(n)$ 的递归关系的一种数学工具。它广泛应用于分析分治算法的时间复杂度。

The Master Theorem provides a method to solve recurrence relations of the form $T(n)=aT\left(\frac{n}{b}\right)+f(n)$. It is widely used in analyzing the time complexity of divide-and-conquer algorithms.

递归关系 | Recurrence Relation

给定递归关系 $T(n)=aT\left(\frac{n}{b}\right)+f(n)$：

Given the recurrence relation $T(n)=aT\left(\frac{n}{b}\right)+f(n)$:

• $a$：子问题的数量。
  • The number of subproblems.
• $b$：每个子问题的规模缩减因子。
  • The factor by which the subproblem size is reduced.
• $f(n)$：划分和合并子问题所需的额外工作量。
  • The additional work done outside the recursive calls, such as dividing and merging the subproblems.

主定理 | Master Theorem

主定理根据函数 $f(n)$ 的增长率，将递归关系分为三种情况。

The Master Theorem classifies the recurrence into three cases based on the growth rate of the function $f(n)$.

情况 1 | Case 1: $f(n)=O\left(n^{{\log }_{b}a-ϵ}\right)$

如果 $f(n)$ 增长速度比 $n^{{\log }_{b}a}$ 慢（即 $ϵ>0$），则：

If $f(n)$ grows slower than $n^{{\log }_{b}a}$ (where $ϵ>0$), then:

$$T(n)=\Theta \left(n^{{\log }_{b}a}\right)$$

情况 2 | Case 2: $f(n)=\Theta \left(n^{{\log }_{b}a}\right)$

如果 $f(n)$ 的增长速度与 $n^{{\log }_{b}a}$ 相同，则：

If $f(n)$ grows at the same rate as $n^{{\log }_{b}a}$, then:

$$T(n)=\Theta \left(n^{{\log }_{b}a}\log n\right)$$

情况 3 | Case 3: $f(n)=\Omega \left(n^{{\log }_{b}a+ϵ}\right)$

如果 $f(n)$ 增长速度比 $n^{{\log }_{b}a}$ 快（即 $ϵ>0$），并且满足 $af\left(\frac{n}{b}\right)\le kf(n)$，其中 $k<1$ 且 $n$ 充分大，则：

If $f(n)$ grows faster than $n^{{\log }_{b}a}$ (where $ϵ>0$), and if $af\left(\frac{n}{b}\right)\le kf(n)$ for some $k<1$ and sufficiently large $n$, then:

$$T(n)=\Theta \left(f(n)\right)$$

示例 | Examples

示例 1 | Example 1: $T(n)=2T\left(\frac{n}{2}\right)+n$

• $a=2$
• $b=2$
• $f(n)=n$
• ${\log }_{b}a={\log }_{2}2=1$

比较 $f(n)$ 和 $n^{{\log }_{b}a}$：

Compare $f(n)$ with $n^{{\log }_{b}a}$:

• $f(n)=n=\Theta (n^{{\log }_{b}a})$

适用于情况 2，因此：

Fits Case 2, thus:

$$T(n)=\Theta \left(n\log n\right)$$

示例 2 | Example 2: $T(n)=4T\left(\frac{n}{2}\right)+n^2$

• $a=4$
• $b=2$
• $f(n)=n^2$
• ${\log }_{b}a={\log }_{2}4=2$

比较 $f(n)$ 和 $n^{{\log }_{b}a}$：

Compare $f(n)$ with $n^{{\log }_{b}a}$:

• $f(n)=n^2=\Theta (n^{{\log }_{b}a})$

适用于情况 2，因此：

Fits Case 2, thus:

$$T(n)=\Theta \left(n^2\log n\right)$$

示例 3 | Example 3: $T(n)=3T\left(\frac{n}{4}\right)+n$

• $a=3$
• $b=4$
• $f(n)=n$
• ${\log }_{b}a={\log }_{4}3\approx 0.79$

比较 $f(n)$ 和 $n^{{\log }_{b}a}$：

Compare $f(n)$ with $n^{{\log }_{b}a}$:

• $f(n)=n=\Omega (n^{{\log }_{b}a+ϵ})$，其中 $ϵ\approx 0.21$

适用于情况 3，并满足 $af\left(\frac{n}{b}\right)\le kf(n)$，因此：

Fits Case 3 and satisfies $af\left(\frac{n}{b}\right)\le kf(n)$, thus:

$$T(n)=\Theta (n)$$

总结 | Summary

主定理提供了一种系统的方法来解决常见的递归关系，特别是那些在分治算法中出现的递归关系。通过理解和应用主定理，可以快速确定算法的时间复杂度，从而优化和分析算法性能。

The Master Theorem provides a systematic method to solve common recurrence relations, especially those appearing in divide-and-conquer algorithms. By understanding and applying the Master Theorem, one can quickly determine the time complexity of algorithms, thus optimizing and analyzing algorithm performance.