分治算法的详解

分治算法（Divide and Conquer）是算法设计中最核心的思想之一。它的逻辑非常符合直觉：把一个大问题拆成几个小问题，分别解决小问题，再把小问题的结果合并起来得到大问题的解。

下面从原理、适用条件、经典实例到编码实现，完整梳理一遍。

一、核心思想与三个步骤

分治算法的执行过程固定为三步：

分解（Divide）：将原问题分解为若干个规模较小、相互独立、与原问题形式相同的子问题。
解决（Conquer）：递归地求解各个子问题。若子问题规模足够小，则直接求解。
合并（Merge）：将各子问题的解合并为原问题的解。
用递归伪代码表达就是：

text
divide_and_conquer(problem):
if problem 足够小:
return 直接求解(problem)
sub_problems = 分解(problem)
sub_results = [divide_and_conquer§ for p in sub_problems]
return 合并(sub_results)
二、适用条件（什么时候能用分治）

不是所有问题都能分治，必须同时满足以下条件：

可分解性：问题能分解为规模更小的同类子问题。
子问题独立：子问题之间不包含公共的子子问题（否则会产生大量重复计算，这时更适合用动态规划）。
可合并性：子问题的解能有效合并成原问题的解。
规模缩小：分解后问题规模确实减小，且能递归到边界条件。
关键区分：分治 vs 动态规划。分治的子问题相互独立（如归并排序左右两半互不影响）；动态规划的子问题相互重叠（如斐波那契数列，需要记忆化避免重复计算）。
三、经典应用实例

分解：把数组从中间切成两半。
解决：递归地对左右两半分别排序。
合并：将两个有序子数组合并成一个有序数组。
时间复杂度：O(n log n)，空间复杂度 O(n)（合并时需要辅助数组）。

分解：选一个基准值（pivot），把数组分成"小于基准"和"大于基准"两部分。
解决：递归排序两部分。
合并：无需合并，原地分区后自然有序。
注意：快排的"分解"依赖基准选择，最坏情况 O(n²)，平均 O(n log n)。它与归并的区别在于分解时做了大量工作，合并时几乎不做事。

分解：与中间元素比较，将搜索范围缩小一半。
解决：递归在某一半中查找。
合并：无需合并，直接返回结果。
这是"分解后只解决一个子问题"的特例，时间复杂度 O(log n)。

将 n 位大整数乘法分解为 3 次 n/2 位乘法（而非朴素算法的 4 次），把复杂度从 O(n²) 降到 O(n^1.585)。

将点集按 x 坐标分成左右两半，分别求最近点对，再处理跨越中线的点对，合并得到全局最近点对。复杂度 O(n log n)。

四、编码实例

实例 1：归并排序（Python）

python
def merge_sort(arr):
# 边界条件：长度 0 或 1 直接返回
if len(arr) <= 1:
return arr

# 1. 分解：从中间切分
mid = len(arr) // 2
left = merge_sort(arr[:mid]) # 2. 解决：递归排序左半
right = merge_sort(arr[mid:]) # 递归排序右半

# 3. 合并：将两个有序数组合并
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

测试

if name == “main”:
data = [38, 27, 43, 3, 9, 82, 10]
print(merge_sort(data)) # [3, 9, 10, 27, 38, 43, 82]
执行过程示意（以 [38, 27, 43, 3] 为例）：

text
[38, 27, 43, 3]
/
[38,27] [43,3]
/ \\ /
[38][27] [43][3]
\\ / \\ /
[27,38] [3,43]
\\ /
[3,27,38,43]
实例 2：快速排序（Python）

python
def quick_sort(arr):
if len(arr) <= 1:
return arr

# 1. 分解：选基准，分区
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot] # 小于基准
middle = [x for x in arr if x == pivot] # 等于基准
right = [x for x in arr if x > pivot] # 大于基准

# 2. 解决 + 3. 合并：递归排序左右并拼接
return quick_sort(left) + middle + quick_sort(right)

测试

data = [38, 27, 43, 3, 9, 82, 10]
print(quick_sort(data)) # [3, 9, 10, 27, 38, 43, 82]
上面这个写法可读性强但额外空间多。工程中常用原地分区（Lomuto 或 Hoare 分区）版本，空间复杂度 O(log n)（递归栈）。
实例 3：二分查找（Python）

python
def binary_search(arr, target):
# arr 必须是有序数组
if not arr:
return -1

mid = len(arr) // 2
if arr[mid] == target:
return mid # 找到，返回索引
elif arr[mid] < target:
# 只解决右半部分这一个子问题
res = binary_search(arr[mid+1:], target)
return mid + 1 + res if res != -1 else -1
else:
# 只解决左半部分
return binary_search(arr[:mid], target)

测试

data = [3, 9, 10, 27, 38, 43, 82]
print(binary_search(data, 27)) # 3
print(binary_search(data, 100)) # -1
工程中更推荐迭代版二分查找，避免切片拷贝和递归开销：

python
def binary_search_iter(arr, target):
lo, hi = 0, len(arr) – 1
while lo <= hi:
mid = (lo + hi) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
lo = mid + 1
else:
hi = mid – 1
return -1
五、复杂度分析要点

用主定理（Master Theorem） 快速判断分治算法复杂度。若递归式为：

text
T(n) = a·T(n/b) + f(n)
其中 a 是子问题个数，n/b 是子问题规模，f(n) 是分解与合并的代价：

情况条件复杂度
归并排序a=2, b=2, f(n)=O(n)O(n log n)
二分查找a=1, b=2, f(n)=O(1)O(log n)
大整数乘法（Karatsuba）a=3, b=2, f(n)=O(n)O(n^log₂3) ≈ O(n^1.585)
六、分治的优缺点

优点：

逻辑清晰，天然适合递归实现，代码可读性好。
易于并行化（子问题独立，可多线程/分布式处理）。
对大数据的排序、搜索、几何问题效率高。
缺点：

递归调用有栈空间开销，深度过大可能栈溢出。
合并步骤可能带来额外空间（如归并排序需要 O(n) 辅助数组）。
子问题若重叠，会重复计算，此时应改用动态规划。