第48章 分治算法

分治算法(Divide and Conquer)核心思想为分而治之：将一个规模大、难以直接求解的原问题，拆分为若干结构相同、规模更小的独立子问题；递归求解所有子问题后，再将子问题的解合并，得到原问题的最终答案。

48.1 基本概念

48.1.1 定义

分治三步核心流程：

1. 分解(Divide)：把原问题均匀拆分为多个独立子问题；
2. 解决(Conquer)：子问题规模足够小时直接求解，否则递归分治；
3. 合并(Combine)：将各个子问题的结果整合，得到原问题解。

48.1.2 分治与递归的关系

分治大多依靠递归实现，但二者不等价：

• 分治一定包含分解+合并两个特有步骤；
• 单纯递归（如朴素斐波那契）无合并逻辑，不属于分治。

48.2 分治通用代码框架

返回类型 divideConquer(问题参数)
{
    // 基本情况：规模足够小，直接返回解
    if (问题规模足够小)
    {
        return 直接求解结果;
    }
    // 1. 分解：拆分出多个子问题
    子问题1, 子问题2... = 分解原问题;
    // 2. 递归求解所有子问题
    解1 = divideConquer(子问题1参数);
    解2 = divideConquer(子问题2参数);
    // 3. 合并子问题答案
    原问题解 = 合并(解1, 解2...);
    return 原问题解;
}

48.3 经典分治算法示例

48.3.1 归并排序(Merge Sort)

1. 分解：将数组从中间切分为左右两个等长子数组；
2. 解决：递归分别排序左右子数组；
3. 合并：双指针合并两个有序数组，生成整体有序数组。

#include <iostream>
using namespace std;

// 合并 [left,mid] 和 [mid+1,right] 两个有序区间
void merge(int arr[], int left, int mid, int right)
{
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int* L = new int[n1];
    int* R = new int[n2];
    // 复制数据到临时数组
    for (int i = 0; i < n1; i++) L[i] = arr[left + i];
    for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];
    int i = 0, j = 0, k = left;
    // 双指针合并
    while (i < n1 && j < n2)
    {
        if (L[i] <= R[j]) arr[k++] = L[i++];
        else arr[k++] = R[j++];
    }
    // 复制剩余元素
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
    delete[] L;
    delete[] R;
}

// 归并排序主函数
void mergeSort(int arr[], int left, int right)
{
    if (left < right)
    {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);    // 左半分治
        mergeSort(arr, mid + 1, right);// 右半分治
        merge(arr, left, mid, right); // 合并有序区间
    }
}

48.3.2 快速排序(Quick Sort)

1. 分解：选取基准pivot，将数组划分成「小于基准」「大于基准」两部分；
2. 解决：递归排序左右两部分；
3. 合并：无需额外合并，划分后数组天然有序。

#include <iostream>
using namespace std;

// 划分函数，返回基准最终下标
int partition(int arr[], int low, int high)
{
    int pivot = arr[high]; // 选最右侧为基准
    int i = low - 1;
    for (int j = low; j < high; j++)
    {
        if (arr[j] <= pivot)
        {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;
}

void quickSort(int arr[], int low, int high)
{
    if (low < high)
    {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);  // 基准左侧
        quickSort(arr, pi + 1, high); // 基准右侧
    }
}

48.3.3 最大子数组和（分治解法）

问题：求数组中连续一段数字的最大和。 分治思路：

1. 分解：数组拆分为左、右两半；
2. 解决：递归求左半最大、右半最大；
3. 合并：计算跨越中点的最大子数组，三者取最大值。

#include <climits>
// 求跨越中点的最大和
int maxCrossingSum(int arr[], int left, int mid, int right)
{
    int sum = 0, leftMax = INT_MIN;
    for (int i = mid; i >= left; i--)
    {
        sum += arr[i];
        if (sum > leftMax) leftMax = sum;
    }
    sum = 0;
    int rightMax = INT_MIN;
    for (int i = mid + 1; i <= right; i++)
    {
        sum += arr[i];
        if (sum > rightMax) rightMax = sum;
    }
    return leftMax + rightMax;
}

int maxSubArraySum(int arr[], int left, int right)
{
    // 基本情况：区间仅一个元素
    if (left == right) return arr[left];
    int mid = left + (right - left) / 2;
    int leftSum = maxSubArraySum(arr, left, mid);
    int rightSum = maxSubArraySum(arr, mid + 1, right);
    int crossSum = maxCrossingSum(arr, left, mid, right);
    // 三者取最大
    return max(max(leftSum, rightSum), crossSum);
}

48.4 分治时间复杂度（主定理）

分治递推标准形式： $T(n) = a \cdot T\left(\frac{n}{b}\right) + f(n)$

• $a$：拆分后的子问题数量；
• $b$：原问题缩小倍数；
• $f(n)$：分解+合并操作的时间复杂度。

主定理三种情况：

1. 若 $f(n) = O(n^c),\ c < \log_b a$，则 $T(n)=O(n^{\log_b a})$
2. 若 $f(n) = O(n^c),\ c = \log_b a$，则 $T(n)=O(n^c \log n)$
3. 若 $f(n) = O(n^c),\ c > \log_b a$，则 $T(n)=O(f(n))$

典型分治复杂度：

• 归并排序：$T(n)=2T(n/2)+O(n) \implies O(n\log n)$
• 快速排序平均：$O(n\log n)$，最坏有序数组$O(n^2)$
• 二分查找：$T(n)=1T(n/2)+O(1) \implies O(\log n)$

48.5 分治算法优缺点

优点

1. 大规模问题拆分为小规模，逻辑清晰；
2. 子问题相互独立，可并行计算；
3. 排序、查找等场景效率优秀。

缺点

1. 递归调用带来栈开销；
2. 合并步骤复杂时性能损耗大；
3. 极小数据规模下，暴力循环比分治更快。

48.6 分治、贪心、动态规划对比

算法	核心逻辑	关键特征	典型例题
分治	拆分子问题，合并结果	子问题独立，必须合并	归并排序、快速排序
贪心	每一步局部最优	无回溯、不存子解	活动选择、Kruskal
动态规划	存重叠子问题最优解	子问题重叠，有后效性	01背包、LCS