编辑“︁分治算法原理”︁

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

== 基本思想 ==  
分治算法遵循三个步骤：  
# '''分解'''（Divide）：将原问题划分为若干个规模较小的子问题。  
# '''解决'''（Conquer）：递归求解子问题。若子问题规模足够小，则直接求解。  
# '''合并'''（Combine）：将子问题的解合并为原问题的解。  

用数学形式表示分治算法的时间复杂度：  
<math>T(n) = aT\left(\frac{n}{b}\right) + f(n)</math>  
其中：  
* <math>a</math> 是子问题数量，  
* <math>\frac{n}{b}</math> 是子问题规模，  
* <math>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算法）：减少乘法次数。  
* '''最近点对问题'''：在平面中寻找距离最近的两个点。  

=== 案例：最近点对问题 ===  
问题描述：给定平面上的<math>n</math>个点，找到距离最近的两个点。  

<mermaid>  
graph TD  
    A[所有点按x坐标排序] --> B[划分为左右两半]  
    B --> C[递归求解左半边最近距离d₁]  
    B --> D[递归求解右半边最近距离d₂]  
    C --> E[取d = min(d₁, d₂)]  
    D --> E  
    E --> F[检查中间带状区域是否存在更近点对]  
</mermaid>  

算法步骤：  
1. 按x坐标排序并划分为左右子集。  
2. 递归计算左右子集的最小距离<math>d</math>。  
3. 合并时检查距离分割线<math>d</math>范围内的点，避免重复计算。  

== 优缺点分析 ==  
{| class="wikitable"  
|+ 分治算法的优缺点  
! 优点 !! 缺点  
|-  
| 简化复杂问题，逻辑清晰 || 递归调用可能栈溢出  
|-  
| 天然适合并行计算 || 子问题重叠时效率低（需结合动态规划）  
|-  
| 许多问题的最优解（如FFT） || 合并步骤可能复杂度高  
|}  

== 总结 ==  
分治算法通过分解、解决、合并三步解决复杂问题，是算法设计中的核心思想之一。理解其原理后，可进一步学习'''动态规划'''（优化重叠子问题）和'''减治算法'''（如二分搜索）。  

{{Algorithms}}

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