主定理 - 天元公学论坛

什么是主定理？

主定理是用来快速计算递归算法时间复杂度的公式。很多分治算法（如归并排序、快速排序）都可以用它来分析。

递归式的标准形式

主定理处理这种形式的递归式：

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

用做蛋糕来理解：

a：把一个大蛋糕分成几份后，需要处理其中几份
n/b：每份蛋糕的大小
f(n)：分割和合并蛋糕花费的时间

三种情况（简化版）

📌 情况1：递归部分占主导

如果 f(n) = O(n^c)，其中 c < log_b(a)
则：T(n) = Θ(n^{log_b(a)})

例子： 归并排序

// T(n) = 2*T(n/2) + O(n)
// a=2, b=2, f(n)=O(n)
// log_b(a) = log_2(2) = 1
// f(n) = O(n^1)，刚好相等，看情况2

📌 情况2：递归和合并一样重要

如果 f(n) = Θ(n^{log_b(a)})
则：T(n) = Θ(n^{log_b(a)} * log n)

例子： 归并排序（正确分析）

void mergeSort(vector<int>& arr, int left, int right) {
    if (left >= right) return;
    int mid = (left + right) / 2;
    mergeSort(arr, left, mid);      // T(n/2)
    mergeSort(arr, mid+1, right);   // T(n/2)
    merge(arr, left, mid, right);   // O(n)
}
// T(n) = 2*T(n/2) + O(n)
// a=2, b=2, log_2(2)=1
// f(n)=n^1，所以 T(n) = O(n log n)

📌 情况3：合并部分占主导

如果 f(n) = Ω(n^c)，其中 c > log_b(a)
则：T(n) = Θ(f(n))

例子： 特殊的递归

// T(n) = 2*T(n/2) + O(n^2)
// a=2, b=2, log_2(2)=1
// f(n)=n^2 > n^1，所以 T(n) = O(n^2)

实际例子对比

// 例1：二分查找
T(n) = T(n/2) + O(1)
a=1, b=2, f(n)=O(1)
log_b(a) = 0, f(n)=n^0
情况2：T(n) = O(log n)

// 例2：普通递归
T(n) = 2*T(n/2) + O(1)  
a=2, b=2, f(n)=O(1)
log_b(a) = 1 > 0
情况1：T(n) = O(n)

// 例3：特殊分治
T(n) = 4*T(n/2) + O(n)
a=4, b=2, f(n)=O(n)
log_b(a) = 2 > 1
情况1：T(n) = O(n^2)

记忆技巧

想象天平⚖️：

左边重（递归重）→ 复杂度看递归：n^{log_b(a)}
平衡（一样重）→ 多乘个log：n^{log_b(a)} * log n
右边重（合并重）→ 复杂度看合并：f(n)

使用步骤

找出 a、b、f(n)
计算 log_b(a)
比较 f(n) 和 n^{log_b(a)}
套用对应情况的公式

主定理让复杂的递归分析变得像查表一样简单！