分治算法复杂度分析

分治算法复杂度分析

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

基本概念

分治算法的复杂度分析通常基于递归关系式（Recurrence Relation）。设：

• 问题规模为$n$
• 每次递归将问题分为$a$个子问题
• 每个子问题的规模为$n/b$
• 分解和合并的复杂度为$f(n)$

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

主定理（Master Theorem）

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

情况	条件	复杂度
1	$f(n)=O(n^{{\log }_{b}a-ϵ})$（$ϵ>0$）	$T(n)=\mathrm{\Theta }(n^{{\log }_{b}a})$
2	$f(n)=\mathrm{\Theta }(n^{{\log }_{b}a}{\log }^{k}n)$（$k\ge 0$）	$T(n)=\mathrm{\Theta }(n^{{\log }_{b}a}{\log }^{k+1}n)$
3	$f(n)=\mathrm{\Omega }(n^{{\log }_{b}a+ϵ})$且$af(n/b)\le cf(n)$（$c<1$）	$T(n)=\mathrm{\Theta }(f(n))$

示例：归并排序

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

复杂度分析示例

快速排序

快速排序的复杂度取决于分区是否平衡：

• 最优情况（每次分区均等）：$T(n)=2T(n/2)+O(n)\Rightarrow O(n\log n)$
• 最差情况（每次分区极不平衡）：$T(n)=T(n-1)+O(n)\Rightarrow O(n^2)$

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

代码示例：二分查找

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

复杂度分析：$T(n)=T(n/2)+O(1)\Rightarrow O(\log n)$（主定理情况2）

实际应用案例

1. 地图渲染：将大地图分割为小块并行渲染后合并 2. 多项式乘法：通过Karatsuba算法将复杂度从$O(n^2)$降至$O(n^{{\log }_{2}3})$ 3. Strassen矩阵乘法：通过分治将矩阵乘法复杂度从$O(n^3)$降至$O(n^{{\log }_{2}7})$

常见误区

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

进阶思考

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