主定理

主定理适用于以下形式的递归方程：$T(n)=aT(n/b)+f(n)$ - $n$：问题的总规模。 - $a$：子问题的个数（要把原问题切成几份）。 - $n/b$：每个子问题的规模（每份是原来的几分之一）。 - $f(n)$：合并消耗（除了递归之外，合并结果或切分问题所花费的时间）。

情况 1：递归拆分占主导 (The waterfall case)

如果 $n^{{\log }_{b}a}$ 的增长速度远大于 $f(n)$：

• 结论：$T(n)=\Theta (n^{{\log }_{b}a})$
• 直观理解：子问题的数量太多或规模缩减太慢，主要的压力都在递归调用上。

情况 2：两股力量势均力敌 (The steady case)

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

• 结论：$T(n)=\Theta (n^{{\log }_{b}a}\log n)$
• 直观理解：这是最常见的情况，比如归并排序。每一层的代价都差不多。

情况 3：合并操作占主导 (The mountain case)

如果 $f(n)$ 的增长速度远大于 $n^{{\log }_{b}a}$：

• 结论：$T(n)=\Theta (f(n))$
• 直观理解：合并操作太重了，递归那点消耗几乎可以忽略不计。