分治算法详解：化繁为简的行为艺术

掌握分治思想，轻松解决复杂问题

什么是分治算法

分治（Divide and Conquer）是一种重要的算法设计思想，其核心是：

将一个复杂的问题分解成若干个规模较小但结构相似的子问题，递归地解决这些子问题，然后将子问题的解合并得到原问题的解。

形象理解

想象你需要统计一本厚书的总字数：

1
2
3
4
5
方法1：一页一页数（暴力）
方法2：分治
  ├── 把书分成两半
  ├── 分别数每一半的字数（递归）
  └── 两半字数相加（合并）

适用条件

分治算法适用于具有以下特征的问题：

  1. 可分解性：问题可以分解成若干个规模较小的相同问题
  2. 子问题独立：子问题之间相互独立，不包含公共子问题
  3. 可合并性：子问题的解可以合并为原问题的解
  4. 存在基准情况：当问题规模足够小时，可以直接求解
graph TD
    A[原问题] --> B[子问题1]
    A --> C[子问题2]
    A --> D[子问题...]
    
    B --> E[解1]
    C --> F[解2]
    D --> G[解...]
    
    E --> H[合并]
    F --> H
    G --> H
    H --> I[最终解]
    
    style A fill:#FFE4B5
    style I fill:#90EE90

分治三步曲

核心框架

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Result divideAndConquer(Problem problem) {
    // 1. 基准情况：问题足够小，直接求解
    if (problem.size <= threshold) {
        return directSolve(problem);
    }
    
    // 2. 分解：将问题分成子问题
    subProblems = divide(problem);
    
    // 3. 递归：解决每个子问题
    for (subProblem : subProblems) {
        subResults.push_back(divideAndConquer(subProblem));
    }
    
    // 4. 合并：将子问题的解合并
    return combine(subResults);
}

三步详解

步骤 名称 作用 关键点
1 Divide（分） 将问题分解为子问题 如何划分？划分几份？
2 Conquer（治） 递归解决子问题 基准情况是什么？
3 Combine（合） 合并子问题的解 如何高效合并？

时间复杂度通用公式

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

  • aa：子问题数量
  • bb：子问题规模缩小的倍数
  • f(n)f(n)：分解和合并的代价

经典问题详解

1. 归并排序

LeetCode 912: 排序数组

问题分析

将一个无序数组排序成有序数组。

分治思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
原数组：[38, 27, 43, 3, 9, 82, 10]
         
      分解（Divide）
         ↓
[38, 27, 43, 3]    [9, 82, 10]
      ↓                 ↓
[38, 27] [43, 3]   [9, 82] [10]
   ↓       ↓         ↓      ↓
[38][27] [43][3]  [9][82]  [10]
   ↓       ↓         ↓      ↓
   解决（Conquer）- 单元素已有序
         ↓
      合并（Combine）
         ↓
[27, 38] [3, 43]  [9, 82]  [10]
      ↓                ↓
[3, 27, 38, 43]   [9, 10, 82]
            ↓
   [3, 9, 10, 27, 38, 43, 82]

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
void mergeSort(vector<int>& nums) {
    vector<int> temp(nums.size());
    mergeSortHelper(nums, temp, 0, nums.size() - 1);
}

void mergeSortHelper(vector<int>& nums, vector<int>& temp, int left, int right) {
    if (left >= right) return;  // 基准情况
    
    int mid = left + (right - left) / 2;
    
    // 分解 + 递归
    mergeSortHelper(nums, temp, left, mid);
    mergeSortHelper(nums, temp, mid + 1, right);
    
    // 合并
    merge(nums, temp, left, mid, right);
}

void merge(vector<int>& nums, vector<int>& temp, int left, int mid, int right) {
    for (int i = left; i <= right; ++i) {
        temp[i] = nums[i];
    }
    
    int i = left, j = mid + 1, k = left;
    while (i <= mid && j <= right) {
        if (temp[i] <= temp[j]) {
            nums[k++] = temp[i++];
        } else {
            nums[k++] = temp[j++];
        }
    }
    
    while (i <= mid) nums[k++] = temp[i++];
    while (j <= right) nums[k++] = temp[j++];
}

复杂度分析

  • 时间：T(n)=2T(n/2)+O(n)=O(nlog⁡n)T(n) = 2T(n/2) + O(n) = O(n \log n)
  • 空间：O(n)O(n) 临时数组

为什么用归并排序？

✅ 稳定排序：相等元素的相对顺序不变
✅ 时间稳定：最好、最坏、平均都是 O(nlog⁡n)O(n \log n)
✅ 适合链表：不需要随机访问
✅ 适合外排序：大文件排序

2. 快速排序

LeetCode 912: 排序数组（另一种解法）

分治思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
原数组：[64, 34, 25, 12, 22, 11, 90]
选择 pivot = 22（随机选择）

      分区（Partition）
             ↓
[12, 11] [22] [64, 34, 25, 90]
  < 22    =      > 22
    ↓             ↓
  递归排序      递归排序
    ↓             ↓
[11, 12]     [25, 34, 64, 90]
         ↓
    合并（无需操作，已有序）
         ↓
[11, 12, 22, 25, 34, 64, 90]

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void quickSort(vector<int>& nums) {
    quickSortHelper(nums, 0, nums.size() - 1);
}

void quickSortHelper(vector<int>& nums, int left, int right) {
    if (left >= right) return;
    
    int pivotIndex = partition(nums, left, right);
    
    quickSortHelper(nums, left, pivotIndex - 1);
    quickSortHelper(nums, pivotIndex + 1, right);
}

int partition(vector<int>& nums, int left, int right) {
    // 随机选择pivot，避免最坏情况
    int randomIndex = left + rand() % (right - left + 1);
    swap(nums[randomIndex], nums[right]);
    
    int pivot = nums[right];
    int i = left - 1;
    
    for (int j = left; j < right; ++j) {
        if (nums[j] <= pivot) {
            swap(nums[++i], nums[j]);
        }
    }
    
    swap(nums[i + 1], nums[right]);
    return i + 1;
}

复杂度分析

  • 时间：平均 O(nlog⁡n)O(n \log n)，最坏 O(n2)O(n^2)
  • 空间：O(log⁡n)O(\log n) 递归栈

快排 vs 归并

特性 快速排序 归并排序
平均时间 O(nlog⁡n)O(n \log n) O(nlog⁡n)O(n \log n)
最坏时间 O(n2)O(n^2) O(nlog⁡n)O(n \log n)
空间复杂度 O(log⁡n)O(\log n) O(n)O(n)
稳定性 ❌ 不稳定 ✅ 稳定
原地排序 ✅ 是 ❌ 否
实际性能 更快（缓存友好） 略慢

3. 最大子数组和

LeetCode 53: 最大子数组和

问题描述

给定一个整数数组，找到具有最大和的连续子数组。

1
2
3
输入：[-2, 1, -3, 4, -1, 2, 1, -5, 4]
输出：6
解释：连续子数组 [4, -1, 2, 1] 的和最大，为 6

分治思路

最大子数组只可能在三个位置：

  1. 完全在左半部分
  2. 完全在右半部分
  3. 跨越中点
1
2
3
4
5
6
7
8
数组：[-2, 1, -3, 4, -1, 2, 1, -5, 4]
              ↓ mid
      左半部分  |  右半部分
               
 左边最大：1    右边最大：4
 跨越中点最大：4 + (-1) + 2 + 1 = 6
 
 最终答案：max(1, 4, 6) = 6
graph TD
    A[整个数组] --> B[左半部分]
    A --> C[右半部分]
    A --> D[跨越中点]
    
    B --> E[递归求解]
    C --> F[递归求解]
    D --> G[线性扫描]
    
    E --> H[取最大值]
    F --> H
    G --> H
    
    H --> I[返回结果]
    
    style D fill:#FFE4B5
    style H fill:#90EE90

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
int maxSubArray(vector<int>& nums) {
    return maxSubArrayHelper(nums, 0, nums.size() - 1);
}

int maxSubArrayHelper(vector<int>& nums, int left, int right) {
    if (left == right) return nums[left];  // 基准情况
    
    int mid = left + (right - left) / 2;
    
    int leftMax = maxSubArrayHelper(nums, left, mid);
    int rightMax = maxSubArrayHelper(nums, mid + 1, right);
    int crossMax = maxCrossing(nums, left, mid, right);
    
    return max({leftMax, rightMax, crossMax});
}

int maxCrossing(vector<int>& nums, int left, int mid, int right) {
    // 从中点向左扩展
    int leftSum = INT_MIN, sum = 0;
    for (int i = mid; i >= left; --i) {
        sum += nums[i];
        leftSum = max(leftSum, sum);
    }
    
    // 从中点向右扩展
    int rightSum = INT_MIN;
    sum = 0;
    for (int i = mid + 1; i <= right; ++i) {
        sum += nums[i];
        rightSum = max(rightSum, sum);
    }
    
    return leftSum + rightSum;
}

复杂度分析

  • 时间：T(n)=2T(n/2)+O(n)=O(nlog⁡n)T(n) = 2T(n/2) + O(n) = O(n \log n)
  • 空间：O(log⁡n)O(\log n) 递归栈

注意：这道题有更优的 O(n)O(n) 动态规划解法，但分治解法是理解分治思想的好例子。

4. 快速幂

LeetCode 50: Pow(x, n)

问题描述

实现 pow(x, n)，即计算 x 的 n 次幂。

暴力 vs 分治

1
2
3
4
5
6
7
8
9
10
计算 2^10：

暴力：2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2  (10次乘法)

分治：
  2^10 = 2^5 × 2^5
  2^5 = 2^2 × 2^2 × 2
  2^2 = 2 × 2

只需要 4 次乘法！

分治思路

xn={xn/2×xn/2n 是偶数xn/2×xn/2×xn 是奇数x^n = \begin{cases} x^{n/2} \times x^{n/2} & n \text{ 是偶数} \\ x^{n/2} \times x^{n/2} \times x & n \text{ 是奇数} \end{cases}

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
double myPow(double x, long long n) {
    if (n < 0) {
        x = 1 / x;
        n = -n;
    }
    return fastPow(x, n);
}

double fastPow(double x, long long n) {
    if (n == 0) return 1.0;  // 基准情况
    
    double half = fastPow(x, n / 2);  // 分治
    
    if (n % 2 == 0) {
        return half * half;           // 偶数
    } else {
        return half * half * x;       // 奇数
    }
}

迭代版本（更优）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
double myPow(double x, long long n) {
    if (n < 0) {
        x = 1 / x;
        n = -n;
    }
    
    double result = 1.0;
    while (n > 0) {
        if (n & 1) {        // n是奇数
            result *= x;
        }
        x *= x;             // x = x^2
        n >>= 1;            // n = n / 2
    }
    return result;
}

复杂度分析

  • 时间：O(log⁡n)O(\log n)
  • 空间：递归 O(log⁡n)O(\log n)，迭代 O(1)O(1)

5. 第K大元素

LeetCode 215: 数组中的第K个最大元素

问题描述

找出数组中第 k 大的元素。

1
2
输入：[3, 2, 1, 5, 6, 4], k = 2
输出：5

分治思路：快速选择

利用快排的 partition 思想，每次可以确定一个元素的最终位置：

1
2
3
4
5
6
7
8
数组：[3, 2, 1, 5, 6, 4]，找第2大（即第5小）

Partition后（假设pivot=4）：
[3, 2, 1] [4] [5, 6]
  0,1,2    3   4,5

pivot在位置3，第5小应该在位置4
所以在右半部分继续找

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int findKthLargest(vector<int>& nums, int k) {
    int targetIndex = nums.size() - k;
    return quickSelect(nums, 0, nums.size() - 1, targetIndex);
}

int quickSelect(vector<int>& nums, int left, int right, int k) {
    if (left == right) return nums[left];
    
    int pivotIndex = partition(nums, left, right);
    
    if (pivotIndex == k) {
        return nums[k];
    } else if (pivotIndex < k) {
        return quickSelect(nums, pivotIndex + 1, right, k);
    } else {
        return quickSelect(nums, left, pivotIndex - 1, k);
    }
}

复杂度分析

  • 时间：平均 O(n)O(n)，最坏 O(n2)O(n^2)
  • 空间：O(1)O(1)

为什么平均是 O(n)？

T(n)=T(n/2)+O(n)=O(n)+O(n/2)+O(n/4)+...=O(2n)=O(n)T(n) = T(n/2) + O(n) = O(n) + O(n/2) + O(n/4) + ... = O(2n) = O(n)

与快排不同，快速选择只需要递归一侧！

6. 逆序对计数

剑指Offer 51: 数组中的逆序对

问题描述

在数组中，如果前面的数大于后面的数，则这两个数构成一个逆序对。

1
2
3
输入：[7, 5, 6, 4]
输出：5
解释：(7,5), (7,6), (7,4), (5,4), (6,4)

分治思路

利用归并排序的过程统计逆序对：

1
2
3
4
5
6
7
8
9
10
11
[7, 5, 6, 4]
     ↓ 分解
[7, 5] [6, 4]
  ↓       ↓
[7][5] [6][4]
  ↓       ↓ 合并时统计
[5,7]   [4,6]  ← 统计了 (7,5), (6,4)
     ↓ 合并时统计
[4, 5, 6, 7]   ← 统计了 (7,4), (7,6), (5,4)

关键：当右边元素先被放入时，左边剩余的都是逆序对

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
int countInversions(vector<int>& nums) {
    vector<int> temp(nums.size());
    return countHelper(nums, temp, 0, nums.size() - 1);
}

int countHelper(vector<int>& nums, vector<int>& temp, int left, int right) {
    if (left >= right) return 0;
    
    int mid = left + (right - left) / 2;
    int count = 0;
    
    count += countHelper(nums, temp, left, mid);
    count += countHelper(nums, temp, mid + 1, right);
    count += mergeAndCount(nums, temp, left, mid, right);
    
    return count;
}

int mergeAndCount(vector<int>& nums, vector<int>& temp, 
                  int left, int mid, int right) {
    for (int i = left; i <= right; ++i) {
        temp[i] = nums[i];
    }
    
    int i = left, j = mid + 1, k = left, count = 0;
    
    while (i <= mid && j <= right) {
        if (temp[i] <= temp[j]) {
            nums[k++] = temp[i++];
        } else {
            nums[k++] = temp[j++];
            count += (mid - i + 1);  // 关键：左边剩余都是逆序对
        }
    }
    
    while (i <= mid) nums[k++] = temp[i++];
    while (j <= right) nums[k++] = temp[j++];
    
    return count;
}

复杂度分析

  • 时间：O(nlog⁡n)O(n \log n)
  • 空间：O(n)O(n)

分治 vs 递归 vs 动态规划

三者关系

graph TD
    A[递归] --> B[分治]
    A --> C[动态规划]
    
    B --> D[子问题独立]
    C --> E[子问题重叠]
    
    D --> F[直接递归求解]
    E --> G[记忆化/自底向上]
    
    style A fill:#FFE4B5
    style B fill:#87CEEB
    style C fill:#90EE90

对比表

特性 递归 分治 动态规划
本质 实现技术 算法思想 算法思想
子问题 - 独立 重叠
求解方式 自顶向下 自顶向下 自底向上/记忆化
典型问题 阶乘 归并排序 斐波那契

如何选择？

  1. 分治：子问题独立，无重复计算
  2. 动态规划：子问题重叠，需要记忆化

复杂度分析：主定理

主定理公式

对于递归式 T(n)=aT(n/b)+f(n)T(n) = aT(n/b) + f(n)，设 c=log⁡bac = \log_b a：

  1. 若 f(n)=O(nc−ϵ)f(n) = O(n^{c-\epsilon})，则 T(n)=Θ(nc)T(n) = \Theta(n^c)
  2. 若 f(n)=Θ(nc)f(n) = \Theta(n^c)，则 T(n)=Θ(nclog⁡n)T(n) = \Theta(n^c \log n)
  3. 若 f(n)=Ω(nc+ϵ)f(n) = \Omega(n^{c+\epsilon})，则 T(n)=Θ(f(n))T(n) = \Theta(f(n))

常见情况

递归式 算法 时间复杂度
T(n)=2T(n/2)+O(n)T(n) = 2T(n/2) + O(n) 归并排序 O(nlog⁡n)O(n \log n)
T(n)=2T(n/2)+O(1)T(n) = 2T(n/2) + O(1) 二分查找 O(log⁡n)O(\log n)
T(n)=T(n/2)+O(n)T(n) = T(n/2) + O(n) 快速选择 O(n)O(n)
T(n)=T(n/2)+O(1)T(n) = T(n/2) + O(1) 二分幂 O(log⁡n)O(\log n)

思维导图

graph TD
    A[分治算法] --> B[排序问题]
    A --> C[搜索问题]
    A --> D[数学问题]
    A --> E[统计问题]
    
    B --> B1[归并排序]
    B --> B2[快速排序]
    
    C --> C1[二分查找]
    C --> C2[第K大元素]
    
    D --> D1[快速幂]
    D --> D2[大整数乘法]
    
    E --> E1[逆序对]
    E --> E2[最大子数组]
    
    style A fill:#FFE4B5
    style B1 fill:#87CEEB
    style B2 fill:#87CEEB
    style C1 fill:#90EE90
    style D1 fill:#DDA0DD

总结

核心要点

  1. 分治三步曲：分解 → 递归 → 合并
  2. 适用条件：子问题独立、可合并、存在基准情况
  3. 时间分析：使用主定理
  4. 优化方向：合并操作是关键

分治模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Result divideAndConquer(Problem problem) {
    // 1. 基准情况
    if (isBaseCase(problem)) {
        return solve(problem);
    }
    
    // 2. 分解
    subProblems = divide(problem);
    
    // 3. 递归解决
    for (sub : subProblems) {
        subResults.push_back(divideAndConquer(sub));
    }
    
    // 4. 合并
    return combine(subResults);
}

常见问题分类

类型 问题 合并方式
排序 归并、快排 双指针合并
搜索 二分查找 直接返回
数学 快速幂 乘法
统计 逆序对 计数累加
优化 最大子数组 取最大值

推荐阅读：