编辑“︁分治算法”︁

{{DISPLAYTITLE:分治算法}}  
'''分治算法'''（Divide and Conquer）是计算机科学中一种重要的算法设计范式，通过将复杂问题分解为多个相同或相似的子问题，递归解决子问题后合并结果，最终得到原问题的解。其核心思想可概括为“分而治之”，适用于许多经典问题如排序、搜索和数学计算等。

== 核心思想 ==  
分治算法通常遵循以下三个步骤：  
1. '''分解'''（Divide）：将原问题划分为若干个规模较小的子问题。  
2. '''解决'''（Conquer）：递归求解子问题。若子问题规模足够小，则直接求解。  
3. '''合并'''（Combine）：将子问题的解合并为原问题的解。  

数学形式化表示为：若问题规模为<math>n</math>，分解为<math>a</math>个子问题，每个子问题规模为<math>n/b</math>，合并步骤的时间复杂度为<math>f(n)</math>，则总时间复杂度为：  
<math>T(n) = aT\left(\frac{n}{b}\right) + f(n)</math>

== 代码示例 ==  
以下以'''归并排序'''为例展示分治算法的实现：

<syntaxhighlight lang="python">  
def merge_sort(arr):  
    if len(arr) <= 1:  
        return arr  
    # 分解步骤  
    mid = len(arr) // 2  
    left = merge_sort(arr[:mid])  
    right = merge_sort(arr[mid:])  
    # 合并步骤  
    return merge(left, right)  

def merge(left, right):  
    result = []  
    i = j = 0  
    while i < len(left) and j < len(right):  
        if left[i] < right[j]:  
            result.append(left[i])  
            i += 1  
        else:  
            result.append(right[j])  
            j += 1  
    result.extend(left[i:])  
    result.extend(right[j:])  
    return result  

# 示例输入与输出  
arr = [38, 27, 43, 3, 9, 82, 10]  
print("排序前:", arr)  
print("排序后:", merge_sort(arr))  
</syntaxhighlight>  

'''输出：'''  
<pre>  
排序前: [38, 27, 43, 3, 9, 82, 10]  
排序后: [3, 9, 10, 27, 38, 43, 82]  
</pre>  

=== 代码解释 ===  
1. '''分解'''：将数组递归划分为左右两半，直到子数组长度为1。  
2. '''合并'''：按序合并两个已排序的子数组，通过双指针遍历比较元素。  

== 实际应用案例 ==  
分治算法在以下场景中广泛应用：  
* '''快速排序'''：通过选取基准值划分数组，递归排序子数组。  
* '''二分查找'''：在有序数组中不断折半缩小搜索范围。  
* '''大整数乘法'''（如Karatsuba算法）：将大数分解为高位和低位部分计算。  
* '''最近点对问题'''：将平面点集划分为左右两部分，分别求解后合并结果。  

== 时间复杂度分析 ==  
分治算法的时间复杂度通常通过'''主定理'''（Master Theorem）分析。以归并排序为例：  
* 分解为2个子问题（<math>a=2</math>），规模减半（<math>b=2</math>），合并步骤为<math>O(n)</math>。  
* 根据主定理，时间复杂度为<math>O(n \log n)</math>。  

<mermaid>  
graph TD  
    A[原问题] --> B[子问题1]  
    A --> C[子问题2]  
    B --> D[子子问题1]  
    B --> E[子子问题2]  
    C --> F[子子问题3]  
    C --> G[子子问题4]  
    D --> H[解1]  
    E --> I[解2]  
    F --> J[解3]  
    G --> K[解4]  
    H & I --> L[合并解1+2]  
    J & K --> M[合并解3+4]  
    L & M --> N[最终解]  
</mermaid>  

== 优缺点 ==  
'''优点：'''  
* 简化复杂问题，降低时间复杂度（如从<math>O(n^2)</math>优化到<math>O(n \log n)</math>）。  
* 天然适合并行计算，子问题可独立求解。  

'''缺点：'''  
* 递归调用可能引入栈溢出风险。  
* 合并步骤的实现可能增加额外空间开销（如归并排序需<math>O(n)</math>辅助空间）。  

== 练习建议 ==  
1. 实现快速排序算法，分析其分治过程。  
2. 使用分治法解决“最大子数组和”问题（Kadane算法的分治版本）。  
3. 尝试用分治思想优化斐波那契数列计算（尽管动态规划更高效）。  

分治算法是理解递归和高效问题求解的基石，掌握其思想能显著提升解决复杂问题的能力。

[[Category:计算机科学]]
[[Category:面试技巧]]
[[Category:算法基础]]