编辑“︁分治算法复杂度分析”︁

= 分治算法复杂度分析 =

分治算法（Divide and Conquer）是一种重要的算法设计范式，通过将问题分解为更小的子问题、递归求解子问题，再将子问题的解合并得到原问题的解。理解其时间复杂度分析对优化算法至关重要。

== 基本概念 ==
分治算法的复杂度分析通常基于'''递归关系式'''（Recurrence Relation）。设：
* 问题规模为<math>n</math>
* 每次递归将问题分为<math>a</math>个子问题
* 每个子问题的规模为<math>n/b</math>
* 分解和合并的复杂度为<math>f(n)</math>

则递归关系式为：
<math>T(n) = a \cdot T\left(\frac{n}{b}\right) + f(n)</math>

== 主定理（Master Theorem） ==
主定理是分析分治算法复杂度的通用工具，适用于形如<math>T(n) = aT(n/b) + f(n)</math>的递归式。其三种情况如下：

{| class="wikitable"
|-
! 情况 !! 条件 !! 复杂度
|-
| 1 || <math>f(n) = O(n^{\log_b a - \epsilon})</math>（<math>\epsilon > 0</math>） || <math>T(n) = \Theta(n^{\log_b a})</math>
|-
| 2 || <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>
|-
| 3 || <math>f(n) = \Omega(n^{\log_b a + \epsilon})</math>且<math>af(n/b) \leq cf(n)</math>（<math>c < 1</math>） || <math>T(n) = \Theta(f(n))</math>
|}

=== 示例：归并排序 ===
归并排序的递归式为<math>T(n) = 2T(n/2) + O(n)</math>，对应主定理情况2（<math>a=2, b=2, f(n)=n</math>），因此复杂度为<math>O(n \log n)</math>。

== 复杂度分析示例 ==
=== 快速排序 ===
快速排序的复杂度取决于分区是否平衡：
* 最优情况（每次分区均等）：<math>T(n) = 2T(n/2) + O(n) \Rightarrow O(n \log n)</math>
* 最差情况（每次分区极不平衡）：<math>T(n) = T(n-1) + O(n) \Rightarrow O(n^2)</math>

<mermaid>
graph TD
    A[原始数组] --> B[选择基准]
    B --> C[分区操作]
    C --> D[左子数组]
    C --> E[右子数组]
    D --> F[递归排序]
    E --> G[递归排序]
    F --> H[合并结果]
    G --> H
</mermaid>

=== 代码示例：二分查找 ===
<syntaxhighlight lang="python">
def binary_search(arr, target, low, high):
    if low > high:
        return -1  # 未找到
    mid = (low + high) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] > target:
        return binary_search(arr, target, low, mid - 1)  # 左半部分
    else:
        return binary_search(arr, target, mid + 1, high)  # 右半部分

# 示例
arr = [1, 3, 5, 7, 9]
print(binary_search(arr, 5, 0, len(arr)-1))  # 输出: 2
</syntaxhighlight>
复杂度分析：<math>T(n) = T(n/2) + O(1) \Rightarrow O(\log n)</math>（主定理情况2）

== 实际应用案例 ==
1. '''地图渲染'''：将大地图分割为小块并行渲染后合并
2. '''多项式乘法'''：通过Karatsuba算法将复杂度从<math>O(n^2)</math>降至<math>O(n^{\log_2 3})</math>
3. '''Strassen矩阵乘法'''：通过分治将矩阵乘法复杂度从<math>O(n^3)</math>降至<math>O(n^{\log_2 7})</math>

== 常见误区 ==
* 误认为所有分治算法的复杂度都是<math>O(n \log n)</math>（实际取决于递归结构和合并成本）
* 忽略递归栈的空间复杂度（如快速排序最差需<math>O(n)</math>栈空间）
* 未验证主定理的适用条件（尤其是情况3的规则性条件）

== 进阶思考 ==
对于无法直接应用主定理的递归式（如<math>T(n) = T(n/2) + T(n/4) + n</math>），可使用'''递归树法'''或'''Akra-Bazzi定理'''进一步分析。

[[Category:算法复杂度分析]]

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