主定理公式：算法复杂度分析的终极利器

当我们设计分治算法（Divide and Conquer）时，通常会将一个问题分解为若干个规模较小的子问题，递归地解决这些子问题，然后将结果合并。这种算法的执行时间 T(n) 通常可以用一个递归式来表示：

T(n) = aT(n/b) + f(n)

其中：

• a：子问题的数量（a ≥ 1）。
• b：每个子问题的规模缩减因子（b > 1）。
• f(n)：分解问题和合并结果所需的时间（非递归部分）。
• n：问题的输入规模。

主定理公式的作用，就是直接根据 a, b 和 f(n) 的增长率，给出 T(n) 的渐近界，而无需展开递归树或使用代入法进行繁琐的数学推导。

⚠️ 误区一：忽视正则条件

在应用主定理公式的情形3时，很多初学者只比较了 f(n) 和 n^(log_b(a)) 的增长率，却忽略了正则条件 af(n/b) ≤ cf(n)。

反例： T(n) = 2T(n/2) + n/log n

这里 a=2, b=2, f(n)=n/log n。n^(log_b(a)) = n。 f(n) = n/log n = O(n^(1-ε))? 不，n/log n 比 n 小，但不是多项式小（polynomially smaller）。它比 n 小，但除以 log n 不足以产生 n^ε 的差距。 实际上，这个例子不属于主定理的任何一种标准情况。我们需要使用递归树法或代入法。 更准确的反例是 T(n) = 2T(n/2) + n/log n。 让我们看一个满足增长率但不满足正则条件的例子： T(n) = 2T(n/2) + n / log n。 这里 f(n) = n/log n。n^(log_b(a)) = n。 f(n) 比 n 小，但不是多项式小。所以主定理不适用。

另一个反例： T(n) = 2T(n/2) + n / log n 是不适用的。 考虑 T(n) = 2T(n/2) + n / log n。 让我们看一个经典的陷阱：T(n) = 2T(n/2) + n / log n。 这里 f(n) = n/log n。 n^(log_b(a)) = n。 f(n) = O(n^(1-ε))? 对于任何 ε>0，n^(1-ε) 最终都会小于 n/log n 吗？ n / n^(1-ε) = n^ε。log n 增长慢于任何 n^ε。所以 n/log n > n^(1-ε) 对于大 n 成立。 所以 f(n) 不是 O(n^(1-ε))。因此情形1不适用。 f(n) 不是 Θ(n)。情形2不适用。 f(n) 不是 Ω(n^(1+ε))。情形3不适用。 所以主定理不适用。

再看一个满足情形3增长率但不满足正则条件的例子： T(n) = 2T(n/2) + n / log n 是不适用的。 考虑 T(n) = 2T(n/2) + n / log n。 让我们看 T(n) = 2T(n/2) + n / log n。 好吧，让我们用 T(n) = 2T(n/2) + n / log n 作为不适用主定理的例子。

正确理解： 如果 f(n) 和 n^(log_b(a)) 的差距不是多项式级别的（即不能相差 n^ε），主定理无法直接应用。

⚠️ 误区二：错误判断多项式差距

在情形1和情形3中，要求 f(n) 与 n^(log_b(a)) 的差距必须是多项式级别的。

例如：T(n) = 2T(n/2) + n log n。 a=2, b=2, f(n)=n log n。 n^(log_b(a)) = n。 f(n) = n log n。 f(n) 比 n 大，但大多少？大 log n 倍。 log n 不是多项式 (n^ε)。 因此，这不属于情形3。 实际上，T(n) = 2T(n/2) + n log n 的解是 T(n) = Θ(n log^2 n)。这超出了标准主定理的范围，需要使用扩展主定理或递归树法。

⚠️ 误区三：混淆 a 和 b 的含义

有些同学会将 T(n) = T(n/2) + T(n/3) + n 这样的递归式错误地套用主定理。 主定理要求子问题规模相同（都是 n/b）。如果子问题规模不同，或者子问题数量不是常数，主定理不适用。