模块 1 · 算法概述 与 递归分治

自学起点 · 从遗忘基础到考试答题

先补的数学

对数解决“反复折半”的层数问题：n 连续减半，约 log₂n 次到 1；等差求和 1+⋯+n=n(n+1)/2；递归树 T(n)=2T(n/2)+n 的每层工作量为 n，共约 log₂n 层，因此 Θ(n log n)。

手算例题 · 二分搜索

有序数组 [1,3,5,8,10] 查找 8。先看索引 2，值 5，小于 8，目标只能在右半边；再看索引 3，值 8，找到。循环始终保持“若目标存在，它在当前搜索区间”的不变式。迭代时间 O(log n)，额外空间 O(1)。

0 · 课程与考核CH01 S1–5; Review S93

1 · 算法是什么CH01 S26–33

算法分类：数值型算法（基本运算为算术运算）与非数值型算法。算法与数据结构的关系：算法 + 数据结构 = 程序；数据的逻辑结构与存储结构共同决定实现方式。

2 · 复杂性计量与渐近符号CH01 S34–58; Review S6–14

复杂性 = 时间复杂性 + 空间复杂性。同一算法运行时间受硬件、语言、输入数据影响，所以只比较增长趋势：

复杂性层次：\(1\prec\log n\prec n\prec n\log n\prec n^2\prec n^3\prec\dots\prec2^n\prec n!\)（按渐近增长快慢排序，\(f\prec g\) 表示 \(f=o(g)\)）。多项式时间算法（n 在底数位置）被视为“可解”；指数/阶乘级（n 在指数上）被认为不可承受。

3 · 分析法则与常见函数阶CH01 S61–84

4 · 经典计算题：机器提速问题 ★（历年必考原型）CH01 S73–74; Review S97–100

5 · 递归：概念与四大例题CH02 S3–38

三种适用场景：问题定义是递归的（阶乘、Fibonacci）；数据结构是递归的（二叉树遍历）；求解过程是递归的（Hanoi、全排列）。

6 · 分治法：思想与适用条件CH02 S39–49

7 · Master 定理 ★★（大题必考）CH02 S51; Review S21

8 · 分治六大经典算法

8.1 二分搜索 O(log n)

已排序数组取中间元素比较，每次规模减半。最坏 while 执行 O(log n) 次、每次 O(1) → O(log n)。变体题（作业）：x 不在数组中时返回小于 x 的最大位置 i 与大于 x 的最小位置 j。

8.2 大整数乘法 减乘法次数的思想

朴素 \(O(n^2)\)。分治 \(X=a\cdot2^{n/2}+b,\ Y=c\cdot2^{n/2}+d\)：直接拆要 4 次子乘法；改进为 \[XY=ac\cdot2^n+\big[(a+b)(c+d)-ac-bd\big]2^{n/2}+bd\] 只需 3 次子乘法：\(T(n)=3T(n/2)+O(n)=\Theta(n^{\log_2 3})\approx O(n^{1.59})\)。思想：降低复杂度的关键是减少子乘法次数（判断题：不是减少加法）。

8.3 Strassen 矩阵乘法 O(n^2.81)

分块后同样从 8 次子块乘法降到 7 次（Strassen 的 7 个中间矩阵 M1–M7）：\(T(n)=7T(n/2)+\Theta(n^2)=\Theta(n^{\log_2 7})\approx n^{2.81}\)。已证明 2×2 矩阵 7 次乘法是必要的；当前还有渐近更快的矩阵乘法算法，但具体理论指数会随研究进展变化；课堂重点是 Strassen 的 \(\log_2 7\)。

8.4 棋盘覆盖 分治构造

\(2^k\times2^k\) 棋盘恰有一特殊方格，用 L 型骨牌覆盖其余。分治：十字中心放置一块 L 骨牌（不含特殊方格的三个象限各占一格），把问题化为 4 个 \(2^{k-1}\) 子棋盘。骨牌数 \((4^k-1)/3\)，时间 \(\Theta(4^k)\)。作业常考完整实现。

8.5 快速排序 ★ 划分元决定一切

8.6 线性时间选择 ★ 找第 k 小

8.7 最接近点对 计算几何经典

8.8 循环赛日程表 分治构造题

n=2ᵏ 个选手，每选手与其他 n−1 人各赛一次、每天至多一场，共 n−1 天。分治填表：左上角（前半选手前半程）→ 左下 = 左上 + \(2^{k-1}\) → 右上 = 左下 → 右下 = 左上。8 人日程表是问答真题（Review S107）。

def lower_bound(nums, target):
    """已排序 nums 的第一个 >= target 的下标。O(log n) 时间。"""
    lo, hi = 0, len(nums)
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo

def merge_sort(nums):
    """稳定归并排序。O(n log n) 时间、O(n) 额外空间。"""
    if len(nums) < 2:
        return list(nums)
    mid = len(nums) // 2
    a, b = merge_sort(nums[:mid]), merge_sort(nums[mid:])
    i = j = 0
    out = []
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            out.append(a[i])
            i += 1
        else:
            out.append(b[j])
            j += 1
    return out + a[i:] + b[j:]

def quick_select(nums, k):
    """三路划分求 0-indexed 第 k 小元素。平均 O(n) 时间。"""
    if not 0 <= k < len(nums):
        raise ValueError('k 越界')
    arr = list(nums)
    while True:
        pivot = arr[len(arr) // 2]
        lt = [x for x in arr if x < pivot]
        eq = [x for x in arr if x == pivot]
        gt = [x for x in arr if x > pivot]
        if k < len(lt):
            arr = lt
        elif k < len(lt) + len(eq):
            return pivot
        else:
            k -= len(lt) + len(eq)
            arr = gt

9 · 公式速查（一页纸素材）

10 · 自测（含历年真题）

下一模块：动态规划与贪心——四步法、矩阵连乘/LCS/最大子段和/0-1背包/最优BST；贪心两要素、活动安排及正确性证明、贪心 vs DP 的分界（可拆背包 vs 0-1 背包）。