C / C++ / 系统课时

分治算法怎样拆分问题

分治算法怎样拆分问题

分治不是“多写几次递归”,而是把一个规模较大的问题切成若干彼此独立、结构相同的子问题,分别求解后再合并结果。本节用数组求和展示完整过程,重点看清拆分边界、递归终止条件和合并结果之间的关系。

学习目标

  • 说清分治算法“拆分、求解、合并”的基本模式
  • 能为数组问题设计子问题边界与递归终止条件
  • 能分析分治递归的执行过程和时间复杂度

分治真正拆的是什么

分治法的关键不是把代码分成几段,而是把原问题的输入规模缩小。假设要计算数组区间 data[left..right] 的元素总和,可以在中点 mid 处分成左右两个区间:data[left..mid] 与 data[mid+1..right]。

只要两个子区间互不重叠、合起来又覆盖原区间,就可以分别计算它们的和,最后把两个结果相加。子问题与原问题具有相同形式,因此可以重复使用同一个函数。

数组分治拆分与合并过程

用区间边界建立递归

下面用 C 语言实现分治求和。递归函数每次处理一个闭区间 [left, right];当区间中只剩一个元素时,不再继续拆分,直接返回该元素,这就是终止条件。

c
#include <stdio.h>

int divide_sum(const int data[], int left, int right) {
    if (left == right) {
        return data[left];
    }

    // 用中点把当前区间拆成两个不重叠子区间。
    int mid = left + (right - left) / 2;
    int left_sum = divide_sum(data, left, mid);
    int right_sum = divide_sum(data, mid + 1, right);

    // 当前问题的答案由两个子问题结果合并得到。
    return left_sum + right_sum;
}

int main(void) {
    int data[] = {2, 4, 6, 8, 10, 12, 14, 16};
    int n = (int)(sizeof(data) / sizeof(data[0]));

    int total = divide_sum(data, 0, n - 1);
    printf("sum = %d\n", total);
    return 0;
}

预期输出

text
sum = 72

如果数组为空,就不能直接调用 divide_sum(data, 0, -1),因为这个实现假设传入的区间至少包含一个元素。实际程序应在外层先判断 n > 0,再进入递归。

执行过程为什么不是一直向下

以 8 个元素为例,第一次调用处理 [0,7],拆成 [0,3] 和 [4,7]。左侧继续拆成 [0,1]、[2,3],直到出现 [0,0] 这样的单元素区间。到达终止条件后,递归开始返回,结果才逐层向上合并。

因此一次分治递归同时包含两种方向:调用阶段不断缩小问题,返回阶段不断合并答案。只看“函数调用自己”会忽略一半过程;真正决定算法正确性的,是每层拆分都能覆盖原问题,并且合并操作能还原当前层答案。

怎样判断拆分是否正确

设计分治算法时,可以依次检查三个条件:

  1. 子问题规模必须变小。 否则递归可能永远无法到达终止条件。
  2. 子问题要覆盖原问题。 本例中 [left, mid] 与 [mid+1, right] 合起来必须恰好等于 [left, right]。
  3. 合并规则必须正确。 求和用加法;如果处理的是最大值,则应合并两个子区间的最大值;不同问题的合并操作并不相同。

分治的代价

数组求和本身必须访问每个元素一次,因此总工作量仍是 O(n)O(n)。分治并没有让这个问题比简单循环更快;它的价值在于展示一种可复用的拆解方式,并为归并排序、快速排序、二分相关算法等建立执行模型。

对当前实现而言,递归树高度约为 O(log⁡n)O(\log n),每个元素最终都会成为一个叶子节点,所有层合计完成线性数量的工作。选择分治时,不应只问“能不能递归”,还要看子问题是否独立、合并是否清晰,以及递归开销是否值得。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

分治算法怎样拆分问题

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通