这不是一份题解合集，而是一份“从内存布局和不变量重新理解”的笔记。每个结构尽量回答三个问题：它维护什么不变量、操作为什么正确、复杂度从哪里来；每个算法尽量说清适用条件、失败模式和工程代价。

代码以 Python 3.12 为主，涉及内存布局时用 C++20 对照。复杂度不只看大 O，还会看摊还、期望、常数和缓存。

最后更新：2026-10-23

重学方法：三层视角
复杂度分析：从计数到摊还
线性结构：数组、链表、栈、队列
哈希表：用空间换确定性的概率
树：从 BST 到 B+ 树
堆与优先队列
并查集：几乎常数时间的连通性
图：建模之后，算法才有形状
排序：稳定性、下界与工程混合
查找与字符串
算法设计范式：分治、贪心、DP、回溯
高级结构：Fenwick、线段树、跳表、LRU、布隆过滤器
工程视角：大 O 之外
学习路线与检查清单
附录：复杂度速查与模板

重学方法：三层视角

同一个“数组”，至少有三个层次：

层次	问题	例子
抽象	支持哪些操作？语义是什么？	List：按索引访问、插入、删除
实现	数据在内存里怎么放？	连续内存 + 长度；或节点 + 指针
分析	最坏/平均/摊还复杂度？常数多大？	随机访问 O(1)，头部插入 O(n)

很多人学数据结构只背了第三层的结论，遇到变体就不会。真正有用的是第二层的不变量：

动态数组：0 <= size <= capacity，元素连续存放在 data[0..size)。
单链表：从 head 出发，沿 next 能走完所有节点，最后一个节点 next == None。
二叉搜索树：对任意节点，左子树所有值 < 根，右子树所有值 > 根。
堆：任意节点都小于等于（或大于等于）其子节点。
并查集：每个集合是一棵树，根节点的 parent 指向自己。

不变量一旦写清楚，代码只是在维护它。 调试时也先问：哪条不变量被破坏了？

学习顺序建议：

先能画出内存图（数组、链表、树、图）。
再能写出循环不变量和递归定义。
最后才是背复杂度和模板。

复杂度分析：从计数到摊还

渐进记号

设 $f(n)$、$g(n)$ 是问题规模 $n$ 的函数：

$f(n)=O(g(n))$：存在正常数 $c,n_0$，当 $n\ge n_0$ 时 $0\le f(n)\le cg(n)$。上界。
$f(n)=\Omega(g(n))$：存在正常数 $c,n_0$，当 $n\ge n_0$ 时 $0\le cg(n)\le f(n)$。下界。
$f(n)=\Theta(g(n))$：同时有上界和下界，紧界。
$f(n)=o(g(n))$：$f$ 的增长严格慢于 $g$。

常见增长速度：

$$
O(1) < O(\log n) < O(\sqrt n) < O(n) < O(n\log n) < O(n^2) < O(n^3) < O(2^n) < O(n!)
$$

几个容易混淆的点：

对数底数不影响大 O：$\log_2 n = \Theta(\log_{10} n)$。
大 O 忽略常数，但工程上常数可能差 10 倍。
$O(n)$ 不代表一定比 $O(n\log n)$ 快；$n$ 很小时，低阶项和常数更重要。
最坏、平均、期望、摊还是四种不同口径，不能混着说。

循环怎么数

for i in range(n):          # n 次
    for j in range(i):      # 0+1+...+(n-1) = n(n-1)/2
        pass

复杂度 $O(n^2)$。如果内层是 j in range(0, n, 2)，仍然是 $O(n^2)$，只是常数减半。

i = 1
while i < n:
    i *= 2                  # 1,2,4,...，执行 log2(n) 次

复杂度 $O(\log n)$。

递归：主定理

对形如

$$
T(n)=aT(n/b)+f(n)
$$

的递归（$a\ge1$，$b>1$），令 $c=\log_b a$，比较 $f(n)$ 与 $n^c$：

若 $f(n)=O(n^{c-\epsilon})$，则 $T(n)=\Theta(n^c)$。
若 $f(n)=\Theta(n^c)$，则 $T(n)=\Theta(n^c\log n)$。
若 $f(n)=\Omega(n^{c+\epsilon})$ 且满足正则条件，则 $T(n)=\Theta(f(n))$。

例子：

递归	结果
归并排序 $T(n)=2T(n/2)+O(n)$	$O(n\log n)$
二分查找 $T(n)=T(n/2)+O(1)$	$O(\log n)$
朴素矩阵乘法分治 $T(n)=8T(n/2)+O(n^2)$	$O(n^3)$
二叉树遍历 $T(n)=2T(n/2)+O(1)$	$O(n)$

画递归树也很有用：每层总代价 × 层数，或等比数列求和。

摊还分析：偶尔很贵，但平均不贵

摊还不是“平均情况”，它不依赖输入分布，而是对一串操作的总代价做最坏情况分析。

动态数组扩容

Python list、C++ vector 在容量满时通常会按倍数扩容（常见 2 倍或 1.5 倍）。一次扩容要复制 $n$ 个元素，看似很贵，但把连续 $n$ 次 append 放在一起看：

$$
1+2+4+\cdots+n < 2n
$$

所以总代价 $O(n)$，每次 append 摊还 $O(1)$。注意：**单次最坏仍是 $O(n)$**，实时系统要避免这种抖动。

并查集

路径压缩 + 按秩合并后，$m$ 次操作的复杂度是 $O(m\alpha(n))$，$\alpha$ 是反阿克曼函数，实际可视为常数。

哈希表扩容

负载因子超过阈值时扩容并重新哈希，单次 $O(n)$，但摊还 $O(1)$。

期望复杂度：随机化把最坏情况变罕见

随机化快速排序的期望复杂度是 $O(n\log n)$，但最坏仍是 $O(n^2)$。哈希表在“均匀哈希”假设下期望 $O(1)$，但遇到对抗性输入或糟糕哈希函数会退化到 $O(n)$。

期望复杂度不是保证。 安全敏感场景要考虑哈希碰撞攻击。

空间复杂度

原地算法：额外空间 $O(1)$，如堆排序、快排的原地分区。
递归栈：深度 $h$，如 DFS 最坏 $O(V)$。
归并排序：$O(n)$ 辅助数组。
动态规划：常见 $O(n)$ 或 $O(n^2)$，可通过滚动数组压缩。

隐藏的复杂度陷阱

操作	实际复杂度	说明
`list.append(x)`	摊还 O(1)	扩容时 O(n)
`list.pop()`	O(1)	弹出末尾
`list.pop(0)`	O(n)	所有元素前移
`list.insert(0, x)`	O(n)	所有元素后移
`x in list`	O(n)	线性扫描
`list[a:b]`	O(b-a)	切片复制
`s += t` in loop	O(n^2)	字符串不可变，反复复制
`dict` / `set` 查找	期望 O(1)，最坏 O(n)	哈希冲突
`heapq.heappush`	O(log n)	堆调整

工程上，**一个隐藏的 O(n) 操作放进循环，就能把 O(n) 变成 O(n²)**。

线性结构：数组、链表、栈、队列

数组：连续内存的力量

数组的核心不变量：**元素在内存中连续存放，地址 = base + index × sizeof(element)**。因此：

随机访问 $O(1)$。
缓存友好：顺序扫描时 CPU 预取效率高。
插入/删除中间元素 $O(n)$，因为要搬移。

C++：

int a[10];              // 栈上连续
std::vector<int> v;     // 堆上连续，可扩容
v.reserve(1000);        // 预留容量，避免多次扩容

Python：

a = [1, 2, 3]           # 动态数组，存放的是对象指针
a.append(4)             # 摊还 O(1)
a.insert(0, 0)          # O(n)

Python 的 list 不是“紧凑的 int 数组”，而是指针数组；每个 int 都是独立对象。数值计算场景可以用 array、numpy.ndarray 获得真正的紧凑存储。

动态数组的实现要点

class DynamicArray:
    def __init__(self):
        self._data = [None] * 4
        self._size = 0

    def append(self, x):
        if self._size == len(self._data):
            self._resize(len(self._data) * 2)
        self._data[self._size] = x
        self._size += 1

    def _resize(self, cap):
        new = [None] * cap
        for i in range(self._size):
            new[i] = self._data[i]
        self._data = new

扩容倍数选择：

2 倍：摊还 O(1)，但可能浪费近一半空间。
1.5 倍：空间利用率更好，扩容更频繁。
固定增量：摊还 O(n)，不要用。

链表：用指针换取局部性

单链表节点：

class ListNode:
    __slots__ = ("val", "next")
    def __init__(self, val=0, nxt=None):
        self.val = val
        self.next = nxt

不变量：从 head 出发，沿 next 能遍历所有节点，最后为 None。

常见操作

反转链表（迭代）：

def reverse(head):
    prev, cur = None, head
    while cur:
        nxt = cur.next
        cur.next = prev
        prev, cur = cur, nxt
    return prev

快慢指针找中点 / 判环：

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

合并两个有序链表：

def merge(a, b):
    dummy = tail = ListNode()
    while a and b:
        if a.val <= b.val:
            tail.next, a = a, a.next
        else:
            tail.next, b = b, b.next
        tail = tail.next
    tail.next = a or b
    return dummy.next

数组 vs 链表

维度	数组	链表
随机访问	O(1)	O(n)
头部插入/删除	O(n)	O(1)
已知节点后插入	O(n)	O(1)
缓存局部性	好	差（指针跳转）
额外内存	少（可能预留容量）	每节点一个/两个指针
扩容	需要搬移	不需要

工程结论：大多数场景数组更快，即使理论插入是 O(n)，因为搬移是连续内存的 memmove，而链表遍历是指针追逐 + 缓存 miss。只有在频繁在中间插入/删除、且节点位置已知时，链表才有优势。

栈：后进先出

栈只允许在栈顶操作：push、pop、peek，全部 $O(1)$。

stack = []
stack.append(1)
stack.pop()

应用：

括号匹配、表达式求值。
函数调用栈、DFS 的非递归实现。
单调栈：找“下一个更大元素”。
撤销/重做。

单调栈模板

问题：对每个元素，找右边第一个比它大的元素。

def next_greater(a):
    res = [-1] * len(a)
    st = []                     # 存下标，值单调递减
    for i, x in enumerate(a):
        while st and a[st[-1]] < x:
            res[st.pop()] = x
        st.append(i)
    return res

为什么是 $O(n)$：每个下标最多入栈一次、出栈一次。摊还分析，不是看内层 while 就以为是 $O(n^2)$。

队列：先进先出

普通队列用 collections.deque：

from collections import deque
q = deque()
q.append(1)      # 入队
q.popleft()      # 出队，O(1)

不要用 list.pop(0) 当队列，那是 $O(n)$。

循环队列

固定容量时，用取模复用数组：

class CircularQueue:
    def __init__(self, k):
        self.a = [0] * k
        self.k = k
        self.head = 0
        self.size = 0

    def enqueue(self, x):
        if self.size == self.k:
            return False
        self.a[(self.head + self.size) % self.k] = x
        self.size += 1
        return True

    def dequeue(self):
        if self.size == 0:
            return None
        x = self.a[self.head]
        self.head = (self.head + 1) % self.k
        self.size -= 1
        return x

单调队列：滑动窗口最大值

维护一个下标队列，队列中的值单调递减；窗口右移时，弹出过期下标和比新元素小的尾部。

from collections import deque

def max_sliding_window(a, k):
    q = deque()                 # 存下标
    res = []
    for i, x in enumerate(a):
        while q and q[0] <= i - k:
            q.popleft()
        while q and a[q[-1]] <= x:
            q.pop()
        q.append(i)
        if i >= k - 1:
            res.append(a[q[0]])
    return res

每个元素最多入队/出队一次，$O(n)$。

哈希表：用空间换确定性的概率

哈希表的核心思想：把 key 通过哈希函数映射到桶，平均 $O(1)$ 完成查找、插入、删除。

关键概念

哈希函数：尽量均匀地把 key 映射到 [0, m)。
冲突：不同 key 映射到同一个桶。
负载因子：$\alpha = n/m$，元素数 / 桶数。
扩容：$\alpha$ 超过阈值（如 0.75）时扩大桶数组并重新哈希。

冲突处理

链地址法

每个桶挂一个链表（或红黑树）：

class HashMap:
    def __init__(self, cap=8):
        self.buckets = [[] for _ in range(cap)]
        self.size = 0

    def _idx(self, key):
        return hash(key) % len(self.buckets)

    def put(self, key, value):
        b = self.buckets[self._idx(key)]
        for i, (k, _) in enumerate(b):
            if k == key:
                b[i] = (key, value)
                return
        b.append((key, value))
        self.size += 1
        if self.size / len(self.buckets) > 0.75:
            self._resize(len(self.buckets) * 2)

    def get(self, key, default=None):
        for k, v in self.buckets[self._idx(key)]:
            if k == key:
                return v
        return default

    def _resize(self, cap):
        old = self.buckets
        self.buckets = [[] for _ in range(cap)]
        self.size = 0
        for b in old:
            for k, v in b:
                self.put(k, v)

Python 3.6+ 的 dict 更精巧：用紧凑的 entries 数组保存插入顺序，再用 indices 数组做哈希索引；3.7 起插入顺序成为语言保证。它仍然是开放寻址的一种工程实现。

开放寻址法

冲突时按探测序列找下一个空位：

线性探测：(h + i) % m，缓存友好，但容易聚集。
二次探测：(h + i²) % m，减少聚集，但不保证遍历全表。
双重哈希：(h1 + i·h2) % m，分布更好。

删除不能直接置空，否则会截断探测链，通常用 tombstone（墓碑） 标记。

复杂度与陷阱

操作	平均	最坏
查找	O(1)	O(n)
插入	O(1)	O(n)
删除	O(1)	O(n)

最坏情况来自所有 key 冲突到同一个桶。对抗性输入下，攻击者可以构造大量碰撞，造成哈希碰撞 DoS。

工程注意：

可变对象不能做 key：key 的哈希值变了，就再也找不到了。
自定义对象要实现 __hash__ 和 __eq__，且保持一致：相等对象必须有相同哈希。
不要依赖哈希顺序：除 Python dict 的插入顺序外，多数哈希表无序。
负载因子不是越低越好：太低浪费内存，太高冲突多。

一致性哈希

普通哈希在节点增减时，几乎所有 key 都要重新映射。一致性哈希把节点和 key 映射到一个环上，key 顺时针找到第一个节点：

增加/删除一个节点，只影响相邻区间的 key。
用虚拟节点解决数据倾斜。
常用于分布式缓存、负载均衡、分片存储。

树：从 BST 到 B+ 树

术语

根、叶、父、子、兄弟。
深度：从根到节点的边数；高度：从节点到叶子的最长路径边数。
满二叉树、完全二叉树、平衡二叉树。

遍历

def preorder(root):
    if not root:
        return
    visit(root)
    preorder(root.left)
    preorder(root.right)

def inorder(root):
    if not root:
        return
    inorder(root.left)
    visit(root)
    inorder(root.right)

def postorder(root):
    if not root:
        return
    postorder(root.left)
    postorder(root.right)
    visit(root)

层序遍历用队列：

from collections import deque

def level_order(root):
    if not root:
        return []
    q = deque([root])
    res = []
    while q:
        node = q.popleft()
        res.append(node.val)
        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.right)
    return res

非递归中序（用栈模拟）：

def inorder_iter(root):
    st, cur, res = [], root, []
    while st or cur:
        while cur:
            st.append(cur)
            cur = cur.left
        cur = st.pop()
        res.append(cur.val)
        cur = cur.right
    return res

二叉搜索树 BST

不变量：对任意节点 $x$，左子树所有值 $< x.val$，右子树所有值 $> x.val$。中序遍历得到有序序列。

class TreeNode:
    __slots__ = ("val", "left", "right")
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def search(root, x):
    while root and root.val != x:
        root = root.left if x < root.val else root.right
    return root

def insert(root, x):
    if not root:
        return TreeNode(x)
    if x < root.val:
        root.left = insert(root.left, x)
    elif x > root.val:
        root.right = insert(root.right, x)
    return root

删除分三种情况：

叶子：直接删。
只有一个孩子：用孩子替代。
两个孩子：用右子树最小值（后继）替代，再删除后继。

def delete(root, x):
    if not root:
        return None
    if x < root.val:
        root.left = delete(root.left, x)
    elif x > root.val:
        root.right = delete(root.right, x)
    else:
        if not root.left:
            return root.right
        if not root.right:
            return root.left
        succ = root.right
        while succ.left:
            succ = succ.left
        root.val = succ.val
        root.right = delete(root.right, succ.val)
    return root

BST 的问题：有序插入会退化成链表，高度 $O(n)$，所有操作退化为 $O(n)$。

平衡树

AVL 树

不变量：任意节点左右子树高度差（平衡因子）的绝对值不超过 1。

查找/插入/删除 $O(\log n)$。
插入后最多一次旋转（单旋或双旋）即可恢复平衡；删除可能需要沿路径多次旋转。
四种失衡：LL、RR、LR、RL，对应右旋、左旋、左右双旋、右左双旋。

单旋示例（LL，右旋）：

    z                y
   / \              / \
  y   T4    →      x   z
 / \              / \ / \
x   T3           T1 T2 T3 T4

AVL 高度平衡更严格，查找略快；但插入/删除旋转更多。

红黑树

不变量：

每个节点是红或黑。
根是黑。
叶子（NIL）是黑。
红节点的孩子必须是黑（不能有连续红）。
从任意节点到其所有叶子，黑节点数量相同。

由这些不变量可推出：最长路径不超过最短路径的 2 倍，树高 $O(\log n)$。红黑树插入/删除最多常数次旋转，适合频繁更新的场景。C++ std::map/std::set 常用红黑树，Java TreeMap 也是。

B 树与 B+ 树

磁盘/数据库场景下，瓶颈是页 I/O，不是比较次数。B 树让一个节点存多个 key、多个孩子，降低树高：

每个节点最多 $m$ 个孩子、$m-1$ 个 key。
所有叶子在同一层。
节点大小对齐磁盘页（如 4 KB/16 KB）。

B+ 树：

内部节点只存索引，不存数据。
所有数据在叶子节点，叶子之间用链表连接。
范围查询只需遍历叶子链表。
数据库索引（MySQL InnoDB）常用 B+ 树。

为什么不用 BST 存数据库索引？因为树高每增加一层就多一次随机 I/O；B+ 树用“胖节点”把树高压到 3–4 层。

树的选型

结构	查找	插入/删除	适用
BST	平均 O(log n)，最坏 O(n)	同左	教学、简单场景
AVL	O(log n)	O(log n)	查找远多于更新
红黑树	O(log n)	O(log n)	通用有序容器
B/B+ 树	O(log n)	O(log n)	磁盘、数据库索引
Trie	O(L)	O(L)	字符串前缀查询

堆与优先队列

堆是一棵完全二叉树，用数组存储，不需要指针：

下标 i 的左孩子 2i+1，右孩子 2i+2，父节点 (i-1)//2。
大顶堆：父节点 ≥ 子节点；小顶堆：父节点 ≤ 子节点。
只保证堆序，不保证有序。

核心操作

class MinHeap:
    def __init__(self):
        self.a = []

    def push(self, x):
        self.a.append(x)
        self._sift_up(len(self.a) - 1)

    def pop(self):
        if not self.a:
            raise IndexError("empty")
        top = self.a[0]
        last = self.a.pop()
        if self.a:
            self.a[0] = last
            self._sift_down(0)
        return top

    def _sift_up(self, i):
        while i > 0:
            p = (i - 1) // 2
            if self.a[p] <= self.a[i]:
                break
            self.a[p], self.a[i] = self.a[i], self.a[p]
            i = p

    def _sift_down(self, i):
        n = len(self.a)
        while True:
            l, r = 2 * i + 1, 2 * i + 2
            smallest = i
            if l < n and self.a[l] < self.a[smallest]:
                smallest = l
            if r < n and self.a[r] < self.a[smallest]:
                smallest = r
            if smallest == i:
                break
            self.a[i], self.a[smallest] = self.a[smallest], self.a[i]
            i = smallest

复杂度：

push：$O(\log n)$。
pop：$O(\log n)$。
top：$O(1)$。
建堆：$O(n)$，不是 $O(n\log n)$。

为什么建堆是 O(n)

从最后一个非叶节点向前 sift_down。高度为 $h$ 的节点数最多 $\lceil n/2^{h+1}\rceil$，每个节点下沉代价 $O(h)$：

$$
\sum_{h=0}^{\lfloor\log n\rfloor} \frac{n}{2^{h+1}}h = O(n)
$$

应用

优先队列、任务调度。
Top-K：维护大小为 K 的小顶堆，$O(n\log K)$。
合并 K 个有序链表：堆存每个链表头。
Dijkstra、Prim。
中位数：大顶堆 + 小顶堆。

Python 的 heapq 是小顶堆；大顶堆可以存负数，或自定义包装类。注意元组比较会继续比较第二个元素，可能引发不可比较类型错误：

import heapq
h = []
heapq.heappush(h, (5, "a"))
heapq.heappush(h, (5, "b"))   # 先比 5，再比 "a"/"b"

并查集：几乎常数时间的连通性

并查集（Union-Find / Disjoint Set Union）维护一组不相交集合，支持：

find(x)：找 x 所在集合的代表元。
union(a, b)：合并两个集合。
connected(a, b)：是否同集合。

实现

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.count = n

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]  # 路径压缩
            x = self.parent[x]
        return x

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        self.count -= 1
        return True

两个优化：

路径压缩：查找时把路径上的节点直接挂到根。
按大小/秩合并：小树挂到大树下面，避免树高增长。

同时使用时，$m$ 次操作的复杂度为 $O(m\alpha(n))$，$\alpha(n)$ 是反阿克曼函数，$n$ 在宇宙原子数量级时也不超过 5。

应用

动态连通性、网络节点是否互通。
Kruskal 最小生成树。
账户合并、朋友圈。
网格渗透、岛屿数量（也可 DFS）。
检测无向图环：union 返回 False 说明已连通。

图：建模之后，算法才有形状

表示

表示	空间	判断边	遍历邻居	适用
邻接矩阵	O(V²)	O(1)	O(V)	稠密图、Floyd
邻接表	O(V+E)	O(degree)	O(degree)	稀疏图、大多数场景
边列表	O(E)	O(E)	O(E)	Kruskal、Bellman-Ford

# 邻接表：graph[u] = [(v, w), ...]
graph = [[] for _ in range(n)]
graph[u].append((v, w))

BFS 与 DFS

BFS 用队列，按层扩展，能求无权图最短路径：

from collections import deque

def bfs(graph, src):
    dist = [-1] * len(graph)
    dist[src] = 0
    q = deque([src])
    while q:
        u = q.popleft()
        for v in graph[u]:
            if dist[v] == -1:
                dist[v] = dist[u] + 1
                q.append(v)
    return dist

DFS 用递归或栈，适合连通性、拓扑排序、环检测、回溯：

def dfs(graph, u, seen):
    seen.add(u)
    for v in graph[u]:
        if v not in seen:
            dfs(graph, v, seen)

复杂度都是 $O(V+E)$（邻接表）。

二分图判定

BFS/DFS 染色，相邻节点颜色不同：

def is_bipartite(graph):
    color = [-1] * len(graph)
    for s in range(len(graph)):
        if color[s] != -1:
            continue
        color[s] = 0
        q = deque([s])
        while q:
            u = q.popleft()
            for v in graph[u]:
                if color[v] == -1:
                    color[v] = color[u] ^ 1
                    q.append(v)
                elif color[v] == color[u]:
                    return False
    return True

拓扑排序

有向无环图（DAG）的线性排序，使所有边 $u\to v$ 中 $u$ 排在 $v$ 前。

Kahn 算法

def topo_sort(n, adj):
    indeg = [0] * n
    for u in range(n):
        for v in adj[u]:
            indeg[v] += 1
    q = deque(i for i in range(n) if indeg[i] == 0)
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return order if len(order) == n else []   # 空表示有环

DFS 后序

DFS 完成时把节点压栈，最后反转；同时用三色标记检测环（白/灰/黑）。

应用：课程表、构建依赖、任务调度、编译顺序。

最短路径

Dijkstra

适用：边权非负。贪心：每次取出当前距离最小的未确定节点，它的距离已经是最终值。

import heapq

def dijkstra(graph, src):
    dist = [float("inf")] * len(graph)
    dist[src] = 0
    pq = [(0, src)]
    while pq:
        d, u = heapq.heappop(pq)
        if d != dist[u]:
            continue
        for v, w in graph[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist

复杂度：$O((V+E)\log V)$。为什么不能有负边？因为贪心假设“当前最小距离不会再被更小的负边更新”。

Bellman-Ford

适用：有负边，能检测负环。做 $V-1$ 轮松弛：

def bellman_ford(n, edges, src):
    dist = [float("inf")] * n
    dist[src] = 0
    for _ in range(n - 1):
        changed = False
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                changed = True
        if not changed:
            break
    # 第 V 轮还能松弛，说明存在负环
    for u, v, w in edges:
        if dist[u] + w < dist[v]:
            return None
    return dist

复杂度 $O(VE)$。

Floyd-Warshall

所有点对最短路，允许负边（不能有负环）：

def floyd(n, dist):
    for k in range(n):
        for i in range(n):
            if dist[i][k] == float("inf"):
                continue
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

复杂度 $O(V^3)$，空间 $O(V^2)$。适合小图、稠密图、需要全源最短路。

DAG 最短路

DAG 上按拓扑序松弛，$O(V+E)$，允许负边。因为拓扑序保证前驱先处理。

0-1 BFS

边权只有 0/1 时，用双端队列：0 边入队头，1 边入队尾，$O(V+E)$。

最小生成树

切分性质

对任意把顶点分成两部分的切分，横跨切分的最小边一定属于某棵 MST。这是 Prim 和 Kruskal 的正确性基础。

Kruskal

按边权排序，用并查集判断是否成环：

def kruskal(n, edges):
    dsu = DSU(n)
    total = 0
    used = 0
    for w, u, v in sorted(edges):
        if dsu.union(u, v):
            total += w
            used += 1
            if used == n - 1:
                break
    return total if used == n - 1 else None

复杂度 $O(E\log E)$，适合稀疏图。

Prim

从任意点开始，每次选连接“已选集合”和“未选集合”的最小边：

def prim(graph, start=0):
    n = len(graph)
    used = [False] * n
    pq = [(0, start)]
    total = 0
    while pq:
        w, u = heapq.heappop(pq)
        if used[u]:
            continue
        used[u] = True
        total += w
        for v, wt in graph[u]:
            if not used[v]:
                heapq.heappush(pq, (wt, v))
    return total

复杂度 $O(E\log V)$，适合稠密图。

强连通分量

有向图中，任意两点互相可达的最大点集。Tarjan 用一次 DFS：

def tarjan_scc(n, adj):
    index = 0
    indices = [-1] * n
    low = [0] * n
    on_stack = [False] * n
    stack = []
    comps = []

    def dfs(u):
        nonlocal index
        indices[u] = low[u] = index
        index += 1
        stack.append(u)
        on_stack[u] = True
        for v in adj[u]:
            if indices[v] == -1:
                dfs(v)
                low[u] = min(low[u], low[v])
            elif on_stack[v]:
                low[u] = min(low[u], indices[v])
        if low[u] == indices[u]:
            comp = []
            while True:
                w = stack.pop()
                on_stack[w] = False
                comp.append(w)
                if w == u:
                    break
            comps.append(comp)

    for u in range(n):
        if indices[u] == -1:
            dfs(u)
    return comps

把每个 SCC 缩成一个点，得到 DAG，可用于 2-SAT、依赖分析。

图算法选择

问题	算法	复杂度
无权最短路	BFS	O(V+E)
非负权最短路	Dijkstra	O((V+E)log V)
负权最短路	Bellman-Ford	O(VE)
全源最短路	Floyd	O(V³)
MST	Kruskal / Prim	O(E log E) / O(E log V)
拓扑排序	Kahn / DFS	O(V+E)
强连通分量	Tarjan / Kosaraju	O(V+E)

排序：稳定性、下界与工程混合

排序算法的性质

算法	平均	最坏	空间	稳定	特点
插入排序	O(n²)	O(n²)	O(1)	是	小数组、近乎有序时很快
选择排序	O(n²)	O(n²)	O(1)	否	交换次数少
冒泡排序	O(n²)	O(n²)	O(1)	是	教学用
归并排序	O(n log n)	O(n log n)	O(n)	是	稳定，外排序
快速排序	O(n log n)	O(n²)	O(log n)	否	常数小，缓存友好
堆排序	O(n log n)	O(n log n)	O(1)	否	最坏有保证
计数排序	O(n+k)	O(n+k)	O(k)	是	值域小
基数排序	O(d(n+k))	O(d(n+k))	O(n+k)	是	定长整数/字符串
桶排序	O(n+k)	O(n²)	O(n+k)	是	均匀分布

比较排序的下界

任何基于比较的排序，决策树有 $n!$ 个叶子，高度至少 $\log_2(n!)=\Theta(n\log n)$。所以**比较排序不可能优于 $O(n\log n)$**。计数/基数/桶排序能突破，是因为它们利用了值的结构，而不是只做比较。

插入排序

def insertion_sort(a):
    for i in range(1, len(a)):
        x = a[i]
        j = i - 1
        while j >= 0 and a[j] > x:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = x

近乎有序时接近 $O(n)$，常被用作混合排序的小数组优化。

归并排序

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left = merge_sort(a[:mid])
    right = merge_sort(a[mid:])
    return merge(left, right)

def merge(a, b):
    res = []
    i = j = 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:        # <= 保证稳定
            res.append(a[i]); i += 1
        else:
            res.append(b[j]); j += 1
    res.extend(a[i:])
    res.extend(b[j:])
    return res

稳定、最坏 $O(n\log n)$，但需要 $O(n)$ 额外空间。适合链表排序、外排序、需要稳定性的场景。

快速排序

import random

def quicksort(a, lo=0, hi=None):
    if hi is None:
        hi = len(a) - 1
    if lo >= hi:
        return
    p = partition(a, lo, hi)
    quicksort(a, lo, p - 1)
    quicksort(a, p + 1, hi)

def partition(a, lo, hi):
    r = random.randint(lo, hi)
    a[r], a[hi] = a[hi], a[r]      # 随机 pivot，避免有序输入退化
    pivot = a[hi]
    i = lo
    for j in range(lo, hi):
        if a[j] < pivot:
            a[i], a[j] = a[j], a[i]
            i += 1
    a[i], a[hi] = a[hi], a[i]
    return i

平均 $O(n\log n)$，最坏 $O(n^2)$（每次 pivot 都是最大/最小）。
原地分区，缓存友好，常数小。
不稳定。
工程实现常用三数取中、随机化、小数组切插入排序、递归深度过大切堆排序（introsort）。

堆排序

建堆 $O(n)$，然后反复把堆顶与末尾交换并下沉，$O(n\log n)$，原地但不稳定。适合最坏情况有保证、内存受限的场景。

线性时间排序

计数排序

值域 $[0,k)$：

def counting_sort(a, k):
    cnt = [0] * k
    for x in a:
        cnt[x] += 1
    for i in range(1, k):
        cnt[i] += cnt[i - 1]
    res = [0] * len(a)
    for x in reversed(a):          # 反向保证稳定
        cnt[x] -= 1
        res[cnt[x]] = x
    return res

$O(n+k)$，$k$ 不能太大。

基数排序

按位从低到高做稳定计数排序，$O(d(n+k))$。适合整数、定长字符串。不能直接排浮点数（除非先做规范化）。

桶排序

把元素分到桶里，桶内再排序。数据均匀分布时接近 $O(n)$，分布极不均匀时退化。

工程中的排序

Python sorted/list.sort 使用 Timsort：归并 + 插入，稳定，最坏 $O(n\log n)$，对部分有序数据有优化。
C++ std::sort 通常是 introsort：快排 + 堆排 + 插入排序，不稳定；需要稳定用 std::stable_sort。
数据库/大数据排序要考虑外排序、归并段、磁盘 I/O。

查找与字符串

二分查找

有序数组查找，$O(\log n)$。难点不是代码，而是边界不变量。

def lower_bound(a, x):
    """第一个 >= x 的下标；不存在返回 len(a)"""
    lo, hi = 0, len(a)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if a[mid] < x:
            lo = mid + 1
        else:
            hi = mid
    return lo

不变量：

[0, lo) 中所有元素 < x。
[hi, n) 中所有元素 >= x。
循环结束时 lo == hi，就是答案。

变体：

第一个 > x：把条件改成 a[mid] <= x。
最后一个 <= x：lower_bound(x+1) - 1（整数）或自定义。
查找是否存在：i = lower_bound(a, x); i < n and a[i] == x。

mid = (lo + hi) // 2 在极端大数下可能溢出（C++），用 lo + (hi - lo) // 2。

二分答案

当“判定某个答案是否可行”是单调的，可以对答案二分。例如把包裹按容量装船，求最小容量：

def ship_within_days(weights, days):
    def can(cap):
        need, cur = 1, 0
        for w in weights:
            if w > cap:
                return False
            if cur + w > cap:
                need += 1
                cur = 0
            cur += w
        return need <= days

    lo, hi = max(weights), sum(weights)
    while lo < hi:
        mid = (lo + hi) // 2
        if can(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

KMP

在文本中找模式串，$O(n+m)$。核心是前缀函数 $\pi[i]$：模式串 p[0..i] 的最长真前缀，同时是它的后缀。

def prefix_function(p):
    pi = [0] * len(p)
    for i in range(1, len(p)):
        j = pi[i - 1]
        while j > 0 and p[i] != p[j]:
            j = pi[j - 1]
        if p[i] == p[j]:
            j += 1
        pi[i] = j
    return pi

def kmp_search(text, pat):
    if not pat:
        return 0
    pi = prefix_function(pat)
    j = 0
    for i, ch in enumerate(text):
        while j > 0 and ch != pat[j]:
            j = pi[j - 1]
        if ch == pat[j]:
            j += 1
        if j == len(pat):
            return i - len(pat) + 1
    return -1

理解方式：匹配失败时，不需要回退文本指针，而是利用“已经匹配的部分”的最长 border，把模式串向右滑到下一个可能位置。j = pi[j-1] 就是滑动。

Trie（前缀树）

class TrieNode:
    __slots__ = ("child", "end")
    def __init__(self):
        self.child = {}
        self.end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        cur = self.root
        for ch in word:
            cur = cur.child.setdefault(ch, TrieNode())
        cur.end = True

    def search(self, word):
        cur = self.root
        for ch in word:
            if ch not in cur.child:
                return False
            cur = cur.child[ch]
        return cur.end

    def starts_with(self, prefix):
        cur = self.root
        for ch in prefix:
            if ch not in cur.child:
                return False
            cur = cur.child[ch]
        return True

复杂度 $O(L)$，$L$ 为字符串长度。空间与字符集和公共前缀有关。应用：自动补全、拼写检查、IP 前缀路由、单词搜索。

滚动哈希

把字符串看成多项式：

$$
H(s) = \sum_{i=0}^{L-1} s_i \cdot b^{L-1-i} \bmod M
$$

可以在 $O(1)$ 内求子串哈希（配合前缀哈希和幂），用于 Rabin-Karp、最长重复子串等。

风险：哈希碰撞。工程上用双哈希（两个模数/底数）或直接比较原串确认。不要用滚动哈希做安全校验（如密码、签名）。

字符串算法选择

问题	算法	复杂度
单模式匹配	KMP	O(n+m)
多模式匹配	AC 自动机	O(n+总模式长+匹配数)
前缀查询	Trie	O(L)
子串相等判断	滚动哈希	O(1) 每次
最长公共前缀	Trie / 排序	O(总长) / O(nL log n)

算法设计范式：分治、贪心、DP、回溯

分治

三步：分解、解决子问题、合并。

适用条件：

子问题相互独立。
子问题规模缩小后仍同类型。
合并代价可控。

例子：

归并排序、快速排序。
二分查找。
大整数乘法（Karatsuba）。
最近点对。
快速幂。

快速幂：

def power(a, n, mod):
    res = 1
    while n:
        if n & 1:
            res = res * a % mod
        a = a * a % mod
        n >>= 1
    return res

复杂度 $O(\log n)$。

贪心

每一步选局部最优，希望得到全局最优。难点是证明，常用交换论证：

假设最优解与贪心解在某一步不同。
把最优解改成贪心选择，证明不会变差。
归纳得到贪心解不劣于最优解。

经典：区间调度（按结束时间排序）、Huffman 编码、最小生成树、活动选择。

反例：硬币找零，面值 [1,3,4] 找 6，贪心 4+1+1，最优 3+3。所以贪心不是万能。

区间调度

def max_intervals(intervals):
    intervals.sort(key=lambda x: x[1])
    end = float("-inf")
    count = 0
    for s, e in intervals:
        if s >= end:
            count += 1
            end = e
    return count

按结束时间选，给后面留最多空间。

动态规划

适用条件：

最优子结构：最优解包含子问题的最优解。
重叠子问题：子问题被重复计算。

五步：

定义状态 dp[...] 的含义（一句话说清）。
写转移方程。
确定初始条件和边界。
确定遍历顺序（保证依赖先算）。
返回答案，考虑空间压缩。

0/1 背包

def knapsack(weights, values, W):
    dp = [0] * (W + 1)
    for w, v in zip(weights, values):
        for c in range(W, w - 1, -1):   # 倒序，保证每件只用一次
            dp[c] = max(dp[c], dp[c - w] + v)
    return dp[W]

最长递增子序列 LIS

$O(n^2)$ 版本：

def lis_n2(a):
    dp = [1] * len(a)
    for i in range(len(a)):
        for j in range(i):
            if a[j] < a[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp, default=0)

$O(n\log n)$ 版本维护“长度为 i+1 的递增子序列的最小结尾”：

import bisect

def lis(a):
    tails = []
    for x in a:
        i = bisect.bisect_left(tails, x)
        if i == len(tails):
            tails.append(x)
        else:
            tails[i] = x
    return len(tails)

注意：tails 不是 LIS 本身，只用于求长度。要还原序列需要额外记录前驱。

编辑距离

def edit_distance(s, t):
    n, m = len(s), len(t)
    dp = list(range(m + 1))
    for i in range(1, n + 1):
        prev = dp[0]
        dp[0] = i
        for j in range(1, m + 1):
            cur = dp[j]
            if s[i - 1] == t[j - 1]:
                dp[j] = prev
            else:
                dp[j] = 1 + min(prev, dp[j], dp[j - 1])
            prev = cur
    return dp[m]

状态：dp[i][j] = s[:i] 变成 t[:j] 的最少操作数。空间压缩到 $O(m)$。

最长公共子序列 LCS

def lcs(a, b):
    n, m = len(a), len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[n][m]

区间 DP

以矩阵链乘法为例，dp[i][j] 表示合并区间 [i,j] 的最小代价：

def matrix_chain(p):
    n = len(p) - 1
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float("inf")
            for k in range(i, j):
                cost = dp[i][k] + dp[k + 1][j] + p[i] * p[k + 1] * p[j + 1]
                dp[i][j] = min(dp[i][j], cost)
    return dp[0][n - 1]

区间 DP 的遍历顺序：先长度，再起点，保证子区间先算。

DP 常见错误

状态定义含糊，导致转移漏情况。
初始化错误（空串、0 容量、不可达状态）。
遍历顺序错（0/1 背包用了正序）。
把“恰好”与“至多”混为一谈。
忘记取模或溢出。

回溯

回溯 = 决策树 DFS + 撤销选择。模板：

def backtrack(path, choices):
    if is_solution(path):
        record(path)
        return
    for choice in choices:
        if not valid(choice, path):
            continue
        path.append(choice)          # 做选择
        backtrack(path, next_choices)
        path.pop()                   # 撤销

N 皇后：

def solve_n_queens(n):
    res = []
    cols, diag1, diag2 = set(), set(), set()

    def bt(r, pos):
        if r == n:
            res.append(pos[:])
            return
        for c in range(n):
            if c in cols or (r - c) in diag1 or (r + c) in diag2:
                continue
            cols.add(c); diag1.add(r - c); diag2.add(r + c)
            pos.append(c)
            bt(r + 1, pos)
            pos.pop()
            cols.remove(c); diag1.remove(r - c); diag2.remove(r + c)

    bt(0, [])
    return res

剪枝是回溯的核心：可行性剪枝、最优性剪枝、对称性剪枝。没有剪枝的回溯通常是指数级。

四种范式对比

范式	关键	适用	代价
分治	子问题独立	归并、快排、快速幂	递归/合并开销
贪心	局部最优可证明	区间调度、MST	证明难，容易错
DP	重叠子问题 + 最优子结构	背包、LIS、编辑距离	状态设计、空间
回溯	枚举 + 剪枝	排列组合、N 皇后	指数级最坏

高级结构：Fenwick、线段树、跳表、LRU、布隆过滤器

树状数组 Fenwick

支持单点更新、前缀和查询，$O(\log n)$，常数极小。

核心是 lowbit(i) = i & -i，树状数组的每个节点 tree[i] 管理区间 (i-lowbit(i), i]。

class Fenwick:
    def __init__(self, n):
        self.n = n
        self.t = [0] * (n + 1)

    def add(self, i, delta):
        i += 1
        while i <= self.n:
            self.t[i] += delta
            i += i & -i

    def prefix(self, i):
        """sum[0:i]"""
        s = 0
        while i > 0:
            s += self.t[i]
            i -= i & -i
        return s

    def range_sum(self, l, r):
        """sum[l:r]"""
        return self.prefix(r) - self.prefix(l)

适用：前缀和、区间和、逆序对计数、动态排名。局限：不如线段树灵活，复杂区间操作需要差分技巧。

线段树

把区间递归二分，每个节点维护区间聚合信息（和、最值、gcd 等）。支持区间查询/更新，$O(\log n)$；带懒标记可做区间加/赋值。

             [0,8)
       /              \
    [0,4)            [4,8)
   /     \           /     \
[0,2)   [2,4)     [4,6)   [6,8)

适用：区间最值、区间和、区间加、区间染色、扫描线。代价：实现复杂、常数比 Fenwick 大、空间 $4n$。

跳表 Skip List

用多层链表实现有序集合，查找/插入/删除期望 $O(\log n)$：

底层链表包含所有元素。
上层是下层的“快速通道”，随机决定每个元素是否晋升。
实现比平衡树简单，范围查询友好。
Redis 的有序集合（zset）就用跳表 + 哈希表。

LRU 缓存

要求 get/put 均 $O(1)$：哈希表 + 双向链表。

哈希表：key → 节点。
双向链表：最近使用的在头部，最久未使用的在尾部。
get 命中后把节点移到头部。
put 超容量时删除尾部节点。

class Node:
    __slots__ = ("key", "val", "prev", "next")
    def __init__(self, key=0, val=0):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.map = {}
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def _add_front(self, node):
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        if key not in self.map:
            return -1
        node = self.map[key]
        self._remove(node)
        self._add_front(node)
        return node.val

    def put(self, key, value):
        if key in self.map:
            node = self.map[key]
            node.val = value
            self._remove(node)
            self._add_front(node)
            return
        node = Node(key, value)
        self.map[key] = node
        self._add_front(node)
        if len(self.map) > self.cap:
            lru = self.tail.prev
            self._remove(lru)
            del self.map[lru.key]

布隆过滤器

用位数组 + 多个哈希函数判断“元素可能存在/一定不存在”：

插入：把 k 个哈希位置置 1。
查询：k 个位置都为 1 → 可能存在；否则一定不存在。
没有假阴性，只有假阳性。

误判率近似：

$$
P \approx \left(1-e^{-kn/m}\right)^k
$$

最优哈希个数 $k \approx \frac{m}{n}\ln 2$。

适用：缓存穿透保护、爬虫 URL 去重、数据库前置过滤。不能删除元素（可用计数布隆过滤器变体）。

结构选型

需求	结构
前缀和、单点更新	Fenwick
区间最值/区间加	线段树
有序集合、范围查询	跳表 / 平衡树
O(1) 缓存淘汰	LRU（哈希 + 双向链表）
海量存在性判断	布隆过滤器
字符串前缀	Trie

工程视角：大 O 之外

缓存局部性

现代 CPU 的缓存层级差距很大：L1 几周期，主存上百周期。连续访问和随机访问的实际差距，可能远大于复杂度差异。

数组顺序扫描：预取器友好，缓存命中高。
链表遍历：每次 next 都可能 cache miss。
B+ 树：节点按页对齐，减少随机 I/O。
哈希表：开放寻址通常比链地址缓存友好。

这解释了一个常见现象：理论 O(n) 的数组插入，实际可能比 O(1) 的链表插入更快，因为 memmove 是高度优化的连续拷贝。

常数与实现

Python 的每个 int 都是对象，list 存指针；C++ vector<int> 是紧凑值存储。
Python 函数调用、属性访问、异常处理都有开销。
C++ 的 std::function、虚函数、动态分配也有开销。
编译器优化、分支预测、SIMD 都会影响实际性能。

基准测试方法

先 profile，找到热点，不要凭感觉优化。
固定输入规模、数据分布、硬件、编译选项。
预热，多次运行，看中位数和 P99，不只看一次。
同时记录时间和内存。
用真实数据，不用只测“已排序”“随机”两个极端。
注意 Python 的 GC、C++ 的缓存效应、JIT/解释器差异。

递归的工程问题

Python 默认递归深度约 1000，深递归会 RecursionError。
递归有函数调用开销和栈空间开销。
尾递归在 Python 没有优化；必要时改迭代。
DFS 大图可能爆栈，用显式栈。

并发与并行

多线程不一定加速 CPU 密集任务（Python GIL）。
多进程适合 CPU 密集，但有序列化和内存复制成本。
并行算法要考虑负载均衡、同步开销、伪共享。
分布式场景下，一致性哈希、分片、副本比单机算法更重要。

常见反模式

只看大 O，不看常数和内存。
在循环里做隐式 O(n) 操作。
对非幂等操作重试。
用哈希表存可变的 key。
递归不设终止条件/剪枝。
对有序数据用最坏 pivot 的快排。
用 list.pop(0) 实现队列。
为了“优雅”牺牲可读性，或为了“快”写出无法维护的代码。

学习路线与检查清单

分阶段路线

阶段 1：基础结构

数组、动态数组、链表、栈、队列、双端队列。
哈希表、集合、映射。
能分析循环、递归、摊还复杂度。

阶段 2：树与堆

二叉树遍历、BST、堆、优先队列。
AVL/红黑树理解不变量即可，不必手写完整实现。
并查集。

阶段 3：图

BFS/DFS、拓扑排序、Dijkstra、Bellman-Ford、Floyd。
MST、SCC。
能根据图的性质选算法。

阶段 4：排序与查找

归并、快排、堆排、计数/基数排序。
二分查找及二分答案。
KMP、Trie、滚动哈希。

阶段 5：算法范式

分治、贪心、DP、回溯。
重点练状态定义和正确性证明。

阶段 6：高级与工程

Fenwick、线段树、跳表、LRU、布隆过滤器。
性能分析、缓存、并发、分布式。

刷题方法

不要追求题量，按模式练：

模式	代表问题
双指针	有序数组两数之和、去重、盛水容器
滑动窗口	最长无重复子串、最小覆盖子串
前缀和	子数组和、二维区域和
差分	区间加、航班预订
单调栈	下一个更大元素、柱状图最大矩形
单调队列	滑动窗口最大值
二分答案	装船、分割数组、最小化最大值
回溯	子集、排列、组合、N 皇后
DP	背包、LIS、编辑距离、区间 DP
图	拓扑排序、最短路、连通分量
并查集	连通性、账户合并、冗余连接
堆	Top-K、合并 K 个链表、中位数

每道题做完问自己：

不变量是什么？
为什么这个算法正确？
时间/空间复杂度是多少？
边界条件有哪些？
如果数据规模扩大 10 倍，哪里会先崩？
有没有更简单的实现？

自检清单

能画出数组、链表、树、图的内存结构。
能手写二分查找的四种变体。
能证明 Dijkstra 为什么不能有负边。
能解释建堆为什么是 O(n)。
能解释并查集为什么接近 O(1)。
能写出 0/1 背包、LIS、编辑距离。
能区分贪心和 DP 的适用条件。
能分析递归复杂度（主定理/递归树）。
能根据场景选择哈希表、树、堆、跳表。
能说清缓存局部性对实际性能的影响。

附录：复杂度速查与模板

数据结构复杂度

结构	访问	查找	插入	删除	空间
数组	O(1)	O(n)	O(n)	O(n)	O(n)
动态数组	O(1)	O(n)	摊还 O(1) 尾插	O(n)	O(n)
单链表	O(n)	O(n)	O(1) 已知位置	O(1) 已知前驱	O(n)
哈希表	—	期望 O(1)	期望 O(1)	期望 O(1)	O(n)
BST	O(log n) 平均	O(log n) 平均	O(log n) 平均	O(log n) 平均	O(n)
AVL/红黑树	O(log n)	O(log n)	O(log n)	O(log n)	O(n)
B+ 树	O(log n)	O(log n)	O(log n)	O(log n)	O(n)
堆	O(1) 堆顶	O(n)	O(log n)	O(log n) 堆顶	O(n)
并查集	—	O(α(n))	O(α(n))	—	O(n)
Trie	—	O(L)	O(L)	O(L)	O(总长)

图算法复杂度

算法	时间	空间	限制
BFS	O(V+E)	O(V)	无权
DFS	O(V+E)	O(V)	—
Dijkstra（堆）	O((V+E)log V)	O(V)	非负边
Bellman-Ford	O(VE)	O(V)	可负边，可检测负环
Floyd	O(V³)	O(V²)	可负边，无负环
Kahn	O(V+E)	O(V)	DAG
Kruskal	O(E log E)	O(V)	无向图
Prim（堆）	O(E log V)	O(V)	无向图
Tarjan SCC	O(V+E)	O(V)	有向图

二分查找模板

def lower_bound(a, x):
    lo, hi = 0, len(a)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if a[mid] < x:
            lo = mid + 1
        else:
            hi = mid
    return lo

def upper_bound(a, x):
    lo, hi = 0, len(a)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if a[mid] <= x:
            lo = mid + 1
        else:
            hi = mid
    return lo

并查集模板

class DSU:
    def __init__(self, n):
        self.p = list(range(n))
        self.sz = [1] * n

    def find(self, x):
        while self.p[x] != x:
            self.p[x] = self.p[self.p[x]]
            x = self.p[x]
        return x

    def union(self, a, b):
        a, b = self.find(a), self.find(b)
        if a == b:
            return False
        if self.sz[a] < self.sz[b]:
            a, b = b, a
        self.p[b] = a
        self.sz[a] += self.sz[b]
        return True

参考

Thomas H. Cormen 等，《算法导论》（CLRS）：复杂度、图算法、DP 的严谨基础。
Robert Sedgewick，《算法》：工程视角和实现细节。
Python 官方文档：collections、heapq、bisect、functools。
C++ 参考：std::vector、std::map、std::unordered_map、std::sort。
Big-O Cheat Sheet：https://www.bigocheatsheet.com/
VisuAlgo：https://visualgo.net/

重学数据结构与算法笔记