第8.8.1章: 主定理（附录）

概述

许多算法是递归定义的。为了分析它们的时间复杂度，我们常常写出一个递推关系，描述运行时间如何取决于规模更小的子问题。

主定理是求解下面这类常见递推式的工具：

T(n) = a · T(n / b) + f(n)
      

其中：

• a = 子问题的个数
• b = 问题规模缩小的倍数
• f(n) = 递归调用之外的代价

本附录将教你如何用主定理计算并证明时间复杂度，并给出归并排序和快速排序等例子。

1. 主定理

考虑递推式：

T(n) = a · T(n / b) + f(n)
      

定义临界指数：

n^(log_b(a))
      

把 f(n) 与 n^(log_b(a)) 作比较。

情形 1：f(n) 更小

f(n) = O(n^(log_b(a) - ε))
      

对某个 ε > 0。

则：

T(n) = Θ(n^(log_b(a)))
      

情形 2：f(n) 与临界指数相当

f(n) = Θ(n^(log_b(a)) · ln^k(n))
      

对某个 k ≥ 0。

则：

T(n) = Θ(n^(log_b(a)) · ln^(k+1)(n))
      

情形 3：f(n) 更大

f(n) = Ω(n^(log_b(a) + ε))
      

对某个 ε > 0，并且满足正则性条件。

则：

T(n) = Θ(f(n))
      

2. 例子：归并排序

归并排序把数组分成两半，递归排序每一半，然后用线性时间把它们合并起来。

T(n) = 2 · T(n / 2) + Θ(n)
      

这里：

• a = 2
• b = 2
• f(n) = Θ(n)

临界指数：

n^(log_2(2)) = n
      

由于 f(n) = Θ(n)，属于情形 2。

T(n) = Θ(n · ln(n))
      

3. 例子：快速排序（平均情况）

在平均情况下，快速排序把数组分成两个规模大致相等的子问题，划分耗时线性时间。

T(n) = 2 · T(n / 2) + Θ(n)
      

这与归并排序的递推式相同，因此：

T(n) = Θ(n · ln(n))
      

这就解释了为什么快速排序平均情况下很快。

4. 例子：快速排序（最坏情况）

最坏情况下（枢轴总是最小或最大元素），递推式变成：

T(n) = T(n - 1) + Θ(n)
      

把递推式展开：

T(n) = n + (n - 1) + (n - 2) + ... + 1 = Θ(n^2)
      

它不满足主定理的适用条件，但可以直接计算。

5. 例子：二叉树递归

考虑一个递归处理二叉树的函数：

T(n) = 2 · T(n / 2) + Θ(1)
      

这里：

• a = 2
• b = 2
• f(n) = Θ(1)

临界指数：

n^(log_2(2)) = n
      

由于 f(n) = Θ(1) 比 n 小，属于情形 1。

T(n) = Θ(n)
      

这符合直觉：每个结点访问一次，总时间是线性的。

6. 主定理不适用的情况

主定理不适用于：

• 子问题规模不相等的递推式
• T(n) = T(n - 1) + T(n - 2) 这类递推式
• 分支因子会变化的递推式
• f(n) 不是多项式的递推式

例如斐波那契递推式：

T(n) = T(n - 1) + T(n - 2) + Θ(1)
      

它以 Θ(2^n) 增长，但这无法用主定理推出。

要点

• 主定理求解 T(n) = a·T(n/b) + f(n) 形式的递推式。
• 把 f(n) 与 n^(log_b(a)) 比较以确定属于哪种情形。
• 情形 1：f(n) 更小 → Θ(n^(log_b(a)))。
• 情形 2：f(n) 与临界指数相当 → Θ(n^(log_b(a)) · ln(n))。
• 情形 3：f(n) 更大 → Θ(f(n))（需满足正则性条件）。
• 归并排序与平均情况快速排序都满足 T(n) = 2T(n/2) + Θ(n) → Θ(n·ln(n))。
• 最坏情况快速排序是 Θ(n^2)，不满足主定理的适用条件。
• 并非所有递推式都能用主定理求解（例如斐波那契）。

主定理是分析分治算法的重要工具之一。有了它，你可以快速而严谨地算出一大批递归算法的时间复杂度。