分治算法

6 minIntermediate2026/6/13

分治思想、递推关系与主定理、经典分治算法（归并排序、快速排序、最近点对、大整数乘法）详解。

1. 分治算法思想

1.1 什么是分治

分治算法（Divide and Conquer）是一种将大问题分解为若干个相同结构的子问题，分别求解后合并结果的算法策略。

三个步骤：

分解（Divide）：将原问题分解为若干个规模较小的子问题
解决（Conquer）：递归地求解各子问题，若子问题足够小则直接求解
合并（Combine）：将子问题的解合并为原问题的解

原问题 → 分解 → 子问题1, 子问题2, ..., 子问题k
                              ↓ 递归求解
         合并 ← 子问题1的解, 子问题2的解, ..., 子问题k的解

1.2 分治与递归的关系

递归是一种编程技巧（函数调用自身）
分治是一种算法设计策略（问题分解方式）
分治通常用递归实现，但递归不一定都是分治

# 分治的递归实现模板
def divide_and_conquer(problem):
    # 基线条件：问题足够小，直接求解
    if problem is small_enough:
        return solve_directly(problem)

    # 分解：将问题拆分为子问题
    subproblems = divide(problem)

    # 解决：递归求解子问题
    sub_solutions = [divide_and_conquer(sub) for sub in subproblems]

    # 合并：将子问题的解合并
    return combine(sub_solutions)

1.3 分治的适用条件

问题可以分解为若干个规模较小的相同子问题
子问题相互独立，不包含公共子问题（否则考虑动态规划）
子问题的解可以合并为原问题的解
问题规模缩小到一定程度可以容易地解决

2. 主定理与复杂度分析

2.1 递推关系

分治算法的时间复杂度通常由递推关系描述：

$T(n) = aT(n/b) + f(n)$

其中：

a：子问题的个数
n/b：每个子问题的规模
f(n)：分解和合并的代价

2.2 主定理（Master Theorem）

情况	条件	时间复杂度	示例
情况1	f(n) = O(n^(log_b(a)-ε))	T(n) = Θ(n^log_b(a))	T(n)=2T(n/2)+O(1) → Θ(n)
情况2	f(n) = Θ(n^log_b(a) × log^k(n))	T(n) = Θ(n^log_b(a) × log^(k+1)(n))	T(n)=2T(n/2)+O(n) → Θ(nlogn)
情况3	f(n) = Ω(n^(log_b(a)+ε))	T(n) = Θ(f(n))	T(n)=2T(n/2)+O(n^2) → Θ(n^2)

2.3 常见分治算法复杂度

算法	递推关系	时间复杂度
归并排序	T(n) = 2T(n/2) + O(n)	O(n log n)
快速排序（平均）	T(n) = 2T(n/2) + O(n)	O(n log n)
二分查找	T(n) = T(n/2) + O(1)	O(log n)
Strassen矩阵乘法	T(n) = 7T(n/2) + O(n^2)	O(n^2.81)
最近点对	T(n) = 2T(n/2) + O(n)	O(n log n)

3. 经典分治算法

3.1 归并排序

归并排序是分治思想的典型应用：将数组分为两半，分别排序后合并。

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(merge_sort(arr))  # [3, 9, 10, 27, 38, 43, 82]

归并排序特点：

时间复杂度：O(n log n)，最坏、平均、最好均相同
空间复杂度：O(n)，需要额外空间合并
稳定排序

3.2 快速排序

快速排序通过选择基准元素（pivot）将数组分为两部分，分别排序。

def quick_sort(arr, low=0, high=None):
    """快速排序"""
    if high is None:
        high = len(arr) - 1

    if low < high:
        pivot_idx = partition(arr, low, high)
        quick_sort(arr, low, pivot_idx - 1)
        quick_sort(arr, pivot_idx + 1, high)

    return arr

def partition(arr, low, high):
    """Lomuto分区方案"""
    pivot = arr[high]
    i = low - 1

    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]

    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

# 随机化快速排序，避免最坏情况
import random

def randomized_quick_sort(arr, low=0, high=None):
    """随机化快速排序"""
    if high is None:
        high = len(arr) - 1

    if low < high:
        # 随机选择pivot
        rand_idx = random.randint(low, high)
        arr[rand_idx], arr[high] = arr[high], arr[rand_idx]

        pivot_idx = partition(arr, low, high)
        randomized_quick_sort(arr, low, pivot_idx - 1)
        randomized_quick_sort(arr, pivot_idx + 1, high)

    return arr

# 示例
arr = [10, 7, 8, 9, 1, 5]
print(quick_sort(arr))  # [1, 5, 7, 8, 9, 10]

3.3 最大子数组和

def max_subarray(arr):
    """LeetCode 53: 最大子数组和 - 分治法"""
    def helper(left, right):
        if left == right:
            return arr[left]

        mid = (left + right) // 2

        # 左半部分最大子数组和
        left_max = helper(left, mid)
        # 右半部分最大子数组和
        right_max = helper(mid + 1, right)

        # 跨越中点的最大子数组和
        # 左侧延伸
        left_extend = float('-inf')
        current = 0
        for i in range(mid, left - 1, -1):
            current += arr[i]
            left_extend = max(left_extend, current)

        # 右侧延伸
        right_extend = float('-inf')
        current = 0
        for i in range(mid + 1, right + 1):
            current += arr[i]
            right_extend = max(right_extend, current)

        cross_max = left_extend + right_extend

        return max(left_max, right_max, cross_max)

    return helper(0, len(arr) - 1)

# 示例
print(max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))  # 6 (子数组[4,-1,2,1])

3.4 最近点对问题

def closest_pair(points):
    """最近点对问题 - 分治法"""
    # 按x坐标排序
    points.sort(key=lambda p: p[0])

    def distance(p1, p2):
        return ((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2) ** 0.5

    def helper(pts):
        n = len(pts)
        if n <= 3:
            # 暴力求解
            min_dist = float('inf')
            for i in range(n):
                for j in range(i + 1, n):
                    min_dist = min(min_dist, distance(pts[i], pts[j]))
            return min_dist

        mid = n // 2
        mid_x = pts[mid][0]

        left_min = helper(pts[:mid])
        right_min = helper(pts[mid:])
        d = min(left_min, right_min)

        # 收集横跨中线的点（在d范围内）
        strip = [p for p in pts if abs(p[0] - mid_x) < d]
        strip.sort(key=lambda p: p[1])

        # 检查strip中的点对
        for i in range(len(strip)):
            j = i + 1
            while j < len(strip) and (strip[j][1] - strip[i][1]) < d:
                d = min(d, distance(strip[i], strip[j]))
                j += 1

        return d

    return helper(points)

# 示例
points = [(2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4)]
print(f"最近点对距离: {closest_pair(points):.2f}")  # 1.41

3.5 大整数乘法（Karatsuba算法）

def karatsuba(x, y):
    """Karatsuba大整数乘法"""
    if x < 10 or y < 10:
        return x * y

    n = max(len(str(x)), len(str(y)))
    m = n // 2

    # 分解: x = a*10^m + b, y = c*10^m + d
    power = 10 ** m
    a, b = x // power, x % power
    c, d = y // power, y % power

    # 递归计算三个乘法（而非四个）
    ac = karatsuba(a, c)
    bd = karatsuba(b, d)
    ad_bc = karatsuba(a + b, c + d) - ac - bd

    return ac * (10 ** (2 * m)) + ad_bc * power + bd

# 示例
print(karatsuba(1234, 5678))  # 7006652
print(1234 * 5678)            # 验证: 7006652

4. 分治与其他算法策略的对比

4.1 分治 vs 动态规划

对比维度	分治	动态规划
子问题关系	相互独立	相互重叠
求解方式	自顶向下	自底向上
重复计算	无	通过记忆化避免
典型问题	归并排序、快速排序	背包问题、LCS