编辑“︁主定理”︁

{{DISPLAYTITLE:主定理}}

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

== 定义与形式化描述 ==
主定理处理以下形式的递归关系：
<math>T(n) = aT\left(\frac{n}{b}\right) + f(n)</math>
其中：
* <math>a \geq 1</math>（子问题数量）
* <math>b > 1</math>（问题规模缩小因子）
* <math>f(n)</math> 是合并步骤的复杂度

=== 定理陈述 ===
主定理分为三种情况：
# 若 <math>f(n) = O(n^{\log_b a - \epsilon})</math>（<math>\epsilon > 0</math>），则 <math>T(n) = \Theta(n^{\log_b a})</math>
# 若 <math>f(n) = \Theta(n^{\log_b a} \log^k n)</math>（<math>k \geq 0</math>），则 <math>T(n) = \Theta(n^{\log_b a} \log^{k+1} n)</math>
# 若 <math>f(n) = \Omega(n^{\log_b a + \epsilon})</math>（<math>\epsilon > 0</math>）且满足正则条件 <math>af(n/b) \leq cf(n)</math>（<math>c < 1</math>），则 <math>T(n) = \Theta(f(n))</math>

== 直观理解 ==
主定理通过比较 <math>f(n)</math> 与 <math>n^{\log_b a}</math> 的增长率来决定递归式的主导项：
* '''情况1'''：叶子节点代价主导（递归树最底层操作最多）
* '''情况2'''：各层代价平衡（每层操作量相近）
* '''情况3'''：根节点代价主导（合并步骤最耗时）

<mermaid>
graph TD
    A[比较 f(n) 与 n^log_b a] --> B{f(n)更小?}
    B -->|是| C[情况1: Θ(n^log_b a)]
    B -->|相当| D[情况2: Θ(n^log_b a log n)]
    B -->|更大| E[情况3: Θ(f(n))]
</mermaid>

== 应用示例 ==
=== 归并排序 ===
递归式：<math>T(n) = 2T(n/2) + \Theta(n)</math>
分析：
* <math>a=2, b=2, f(n)=n</math>
* <math>n^{\log_b a} = n^1 = n</math>
* 属于情况2（<math>f(n)=\Theta(n \log^0 n)</math>）
结论：<math>T(n) = \Theta(n \log n)</math>

=== 二分搜索 ===
递归式：<math>T(n) = T(n/2) + \Theta(1)</math>
分析：
* <math>a=1, b=2, f(n)=1</math>
* <math>n^{\log_b a} = n^0 = 1</math>
* 属于情况2（<math>f(n)=\Theta(1 \log^0 n)</math>）
结论：<math>T(n) = \Theta(\log n)</math>

=== 矩阵乘法（Strassen算法） ===
递归式：<math>T(n) = 7T(n/2) + \Theta(n^2)</math>
分析：
* <math>a=7, b=2, f(n)=n^2</math>
* <math>n^{\log_b a} \approx n^{2.807}</math>
* 属于情况1（<math>n^2 = O(n^{2.807 - \epsilon})</math>）
结论：<math>T(n) = \Theta(n^{\log_2 7}) \approx \Theta(n^{2.807})</math>

== 代码示例 ==
=== 分治求最大子数组和 ===
<syntaxhighlight lang="python">
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])
</syntaxhighlight>

时间复杂度分析：
* 递归式：<math>T(n) = 2T(n/2) + \Theta(n)</math>
* 应用主定理情况2，得到 <math>\Theta(n \log n)</math>

== 特殊情况与限制 ==
当 <math>f(n)</math> 与 <math>n^{\log_b a}</math> 的关系不符合三种标准情况时，主定理可能不适用。例如：
* <math>T(n) = 2T(n/2) + n/\log n</math>
* <math>T(n) = T(n/2) + n \log n</math>

此时需要采用其他方法如：
* 递归树法
* Akra-Bazzi定理
* 变量替换法

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

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

[[Category:算法分析]]
[[Category:分治算法]]
[[Category:计算机科学定理]]

[[Category:计算机科学]]
[[Category:数据结构与算法]]