算法通关训练营 · 分治与主定理篇

课程简介

分治（Divide and Conquer）是算法设计四大范式之首，也是归并排序、快速排序、二分查找、最近点对、Strassen 矩阵乘法的共同骨架。本课程带你从"递归树"这一直觉出发，掌握主定理（Master Theorem）这一分析分治复杂度的速查工具，并能在工程里识别递归的代价与风险。

学习目标

• 能把常见分治算法的递归式写成 $T(n)=aT(n/b)+f(n)$
• 熟练套用主定理三情况，直接写出 $\Theta$ 结果
• 用递归树直观验证主定理，理解"哪一层主导总代价"
• 识别主定理失效 / 需小心的递推式，改用求和或换元法
• 理解递归调用栈的工程代价，会用迭代改写避免爆栈

章节概览

1. 分治思想与递归树：分解、解决、合并
2. 主定理三情况与判定器
3. 实战：归并排序与快速排序的复杂度
4. 实战：二分查找与最近点对
5. 主定理的边界与失效情形
6. 递归 vs 迭代：栈、尾递归与爆栈

图：归并排序的递归树——每层代价恒为 n，叠 log₂n 层得 Θ(n log n)

图：分治的通用骨架——几乎所有 Θ(n log n) 算法都长这样

参考代码：课程配套——分治框架模板

def divide_and_conquer(problem):
    """分治通用骨架：能拆到底就直接解，否则分解→递归→合并。"""
    if len(problem) <= 1:               # ② 解决：小到可直接解
        return solve_base(problem)
    halves = split(problem)              # ① 分解
    subs = [divide_and_conquer(h) for h in halves]
    return merge(subs)                   # ③ 合并

def split(arr):                          # 归并：从中间劈成两半
    mid = len(arr) // 2
    return arr[:mid], arr[mid:]

def merge(left, right):                  # 两个有序段线性合并
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    return out + left[i:] + right[j:]