主定理

主定理（Master Theorem）是分析分治算法时间复杂度的核心工具，适用于递归关系式形如 $T (n) = a T (n / b) + f (n)$ 的情况。它为快速确定递归算法的渐近行为提供了系统化方法，广泛应用于算法设计与分析中。

定义与形式化描述[编辑 | 编辑源代码]

主定理处理以下形式的递归关系： $T (n) = a T (\frac{n}{b}) + f (n)$ 其中：

$a \geq 1$ （子问题数量）
$b > 1$ （问题规模缩小因子）
$f (n)$ 是合并步骤的复杂度

定理陈述[编辑 | 编辑源代码]

主定理分为三种情况：

若 $f (n) = O (n^{\log_{b} a - ϵ})$ （ $ϵ > 0$ ），则 $T (n) = Θ (n^{\log_{b} a})$
若 $f (n) = Θ (n^{\log_{b} a} \log^{k} n)$ （ $k \geq 0$ ），则 $T (n) = Θ (n^{\log_{b} a} \log^{k + 1} n)$
若 $f (n) = Ω (n^{\log_{b} a + ϵ})$ （ $ϵ > 0$ ）且满足正则条件 $a f (n / b) \leq c f (n)$ （ $c < 1$ ），则 $T (n) = Θ (f (n))$

直观理解[编辑 | 编辑源代码]

主定理通过比较 $f (n)$ 与 $n^{\log_{b} a}$ 的增长率来决定递归式的主导项：

情况1：叶子节点代价主导（递归树最底层操作最多）
情况2：各层代价平衡（每层操作量相近）
情况3：根节点代价主导（合并步骤最耗时）

应用示例[编辑 | 编辑源代码]

归并排序[编辑 | 编辑源代码]

递归式： $T (n) = 2 T (n / 2) + Θ (n)$ 分析：

$a = 2, b = 2, f (n) = n$
$n^{\log_{b} a} = n^{1} = n$
属于情况2（ $f (n) = Θ (n \log^{0} n)$ ）

结论： $T (n) = Θ (n \log n)$

二分搜索[编辑 | 编辑源代码]

递归式： $T (n) = T (n / 2) + Θ (1)$ 分析：

$a = 1, b = 2, f (n) = 1$
$n^{\log_{b} a} = n^{0} = 1$
属于情况2（ $f (n) = Θ (1 \log^{0} n)$ ）

结论： $T (n) = Θ (\log n)$

矩阵乘法（Strassen算法）[编辑 | 编辑源代码]

递归式： $T (n) = 7 T (n / 2) + Θ (n^{2})$ 分析：

$a = 7, b = 2, f (n) = n^{2}$
$n^{\log_{b} a} \approx n^{2.807}$
属于情况1（ $n^{2} = O (n^{2.807 - ϵ})$ ）

结论： $T (n) = Θ (n^{\log_{2} 7}) \approx Θ (n^{2.807})$

代码示例[编辑 | 编辑源代码]

分治求最大子数组和[编辑 | 编辑源代码]

def max_subarray(nums, l, r):
    if l == r:
        return nums[l]
    
    mid = (l + r) // 2
    left_max = max_subarray(nums, l, mid)
    right_max = max_subarray(nums, mid+1, r)
    
    # 计算跨中点情况
    left_sum = right_sum = -float('inf')
    total = 0
    for i in range(mid, l-1, -1):
        total += nums[i]
        left_sum = max(left_sum, total)
    
    total = 0
    for i in range(mid+1, r+1):
        total += nums[i]
        right_sum = max(right_sum, total)
    
    return max(left_max, right_max, left_sum + right_sum)

# 示例
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subarray(nums, 0, len(nums)-1))  # 输出: 6 (对应子数组 [4,-1,2,1])

时间复杂度分析：

递归式： $T (n) = 2 T (n / 2) + Θ (n)$
应用主定理情况2，得到 $Θ (n \log n)$

特殊情况与限制[编辑 | 编辑源代码]

当 $f (n)$ 与 $n^{\log_{b} a}$ 的关系不符合三种标准情况时，主定理可能不适用。例如：

$T (n) = 2 T (n / 2) + n / \log n$
$T (n) = T (n / 2) + n \log n$

此时需要采用其他方法如：

递归树法
Akra-Bazzi定理
变量替换法

练习问题[编辑 | 编辑源代码]

1. 分析 $T (n) = 3 T (n / 4) + n \log n$ 的复杂度 2. 证明快速排序的平均情况复杂度 $Θ (n \log n)$ （假设分区比例为常数） 3. 设计一个分治算法计算 $x^{n}$ 并分析其复杂度

扩展阅读[编辑 | 编辑源代码]

主定理的严格数学证明（通过递归树或归纳法）
Akra-Bazzi定理的推广形式
分治算法在不同计算模型中的应用（如并行计算）