跳到主要内容

分治算法

分治算法（Divide and Conquer），简称“分而治之”，是通过把大的问题分解成若干个相似的小的问题，然后递归解决这些问题，最后合并子问题的解来解决原问题。

核心步骤​

1. 分解 (Divide)​

将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题。

2. 解决 (Conquer)​

若子问题规模较小而容易被直接解决则直接解决，否则递归地解各个子问题。

3. 合并 (Combine)​

将各个子问题的解合并为原问题的解。

典型算法​

  1. 二分查找 (Binary Search)：虽然是查找，但其核心思想就是分治。
  2. 归并排序 (Merge Sort)：典型的分治排序。
  3. 快速排序 (Quick Sort)：同样基于分治。
  4. 大数乘法 (Karatsuba)。
  5. 矩阵乘法 (Strassen)。

经典例题：归并排序实现​

public void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        // 分
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        // 合
        merge(arr, left, mid, right);
    }
}

private void merge(int[] arr, int l, int m, int r) {
    // 合并两个有序数组
}

核心定理：主定理 (Master Theorem)​

用于分析分治算法的时间复杂度： T(n)=aT(n/b)+f(n)T(n) = aT(n/b) + f(n)

  • a≥1a \ge 1: 子问题个数
  • b>0b > 0: 问题规模缩小的倍数
  • f(n)f(n): 合并子问题的时间支出

练习​

  1. LeetCode 169：多数元素 (可以使用投票算法, 也可以用分治)
  2. LeetCode 53：最大子数组和 (可以使用 DP, 也可以用分治)
  3. LeetCode 215：数组中的第 K 个最大元素 (快速选择属于分治)
  4. LeetCode 23：合并 K 个升序链表 (分治合并)