数据结构与算法 / 系统课时

分治算法的基本框架

分治算法的基本框架

分治算法把大问题拆成结构相同的小问题,分别求解后再合并结果。本课以归并排序为主示例,建立“分解、求解、合并”的固定分析路径,并据此推导时间与空间复杂度。

学习目标

  • 区分递归调用方式与分治设计策略
  • 掌握分解、求解和合并三个阶段
  • 使用递推式分析归并排序复杂度

分治的三个阶段

分治通常满足三个条件:子问题与原问题结构相同、规模严格缩小、子问题之间相对独立。其通用过程是先拆分问题,再递归求解每个子问题,最后合并子结果。

text
solve(problem):
    if problem is small enough:
        return directAnswer
    subProblems = divide(problem)
    subResults = solve each subProblem
    return combine(subResults)

递归是一种实现手段,分治是一种设计策略。阶乘虽然递归调用自身,但每层只产生一个子问题,也没有合并多个子结果,通常不称为分治。

归并排序分治与合并过程

主示例:归并排序

示例采用闭区间 [left, right]。临时数组只创建一次并在递归中复用,避免每次合并重复分配大对象;相等时优先取左侧元素,从而保持排序稳定性。

java
import java.util.Arrays;

public class DivideAndConquerDemo {

    public static void main(String[] args) {
        int[] values = {8, 3, 6, 2, 7, 1, 5, 4};
        mergeSort(values);
        System.out.println(Arrays.toString(values));
    }

    public static void mergeSort(int[] values) {
        if (values == null || values.length <= 1) {
            return;
        }
        int[] temp = new int[values.length];
        mergeSort(values, 0, values.length - 1, temp);
    }

    private static void mergeSort(
        int[] values,
        int left,
        int right,
        int[] temp
    ) {
        if (left >= right) {
            return;
        }

        int middle = left + (right - left) / 2;
        mergeSort(values, left, middle, temp);
        mergeSort(values, middle + 1, right, temp);
        merge(values, left, middle, right, temp);
    }

    private static void merge(
        int[] values,
        int left,
        int middle,
        int right,
        int[] temp
    ) {
        int i = left;
        int j = middle + 1;
        int k = left;

        // 两个子区间此时已经分别有序。
        while (i <= middle && j <= right) {
            temp[k++] = values[i] <= values[j]
                ? values[i++]
                : values[j++];
        }

        while (i <= middle) {
            temp[k++] = values[i++];
        }
        while (j <= right) {
            temp[k++] = values[j++];
        }

        for (int index = left; index <= right; index++) {
            values[index] = temp[index];
        }
    }
}

预期输出:

text
[1, 2, 3, 4, 5, 6, 7, 8]

复杂度如何得到

归并排序每次把规模为 n 的问题拆成两个约为 n / 2 的子问题,合并阶段线性扫描当前区间,因此递推式为:

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

递归树共有 O(log n) 层,每层处理元素总量为 O(n),所以时间复杂度是 O(n log n)。临时数组需要 O(n) 空间,递归栈需要 O(log n),总体额外空间仍为 O(n)。

边界与常见错误

闭区间拆分应使用 [left, middle] 和 [middle + 1, right],否则两个元素时可能反复进入相同区间。合并前必须先完成左右递归;主循环结束后,还要复制未耗尽的一侧元素。

中点写成 left + (right - left) / 2,可避免 left + right 在极端情况下溢出。分治并不天然高效,若拆分长期极不均衡,递归深度可能退化为 O(n)。

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

目录与阅读设置

阅读设置

17

记录一个想法

分治算法的基本框架

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

登录哪都通