速查表

第 1 页：概览与复杂度

一份快速参考，助你理解算法、效率与增长率。 阅读或编码时，可将此页置于手边。

什么是算法？

算法是一个清晰、逐步解决问题的过程。

特性	描述
精确性	每个步骤都明确无误
有限性	必须在有限步后停止
有效性	每个步骤机器或人都可执行
确定性	相同输入，相同输出（通常如此）

可以将其想象成一个食谱：

• 输入：食材
• 步骤：说明
• 输出：最终菜肴

核心特性

概念	要问的问题
正确性	它是否总能解决问题？
终止性	它最终会停止吗？
复杂度	它需要多少时间和空间？
清晰性	它是否易于理解和实现？

为什么复杂度很重要

随着输入规模 $n$ 的增加，不同算法的增长方式不同。

增长率	示例算法	当 $n$ 翻倍时的影响
$O(1)$	哈希查找	无变化
$O(\log n)$	二分查找	轻微增加
$O(n)$	线性扫描	翻倍
$O(n\log n)$	归并排序	略高于 2 倍
$O(n^2)$	冒泡排序	变为 4 倍
$O(2^n)$	子集生成	急剧增长
$O(n!)$	暴力排列（穷举）	当 $n>10$ 时基本不可用

度量时间与空间

度量	含义	示例
时间复杂度	操作次数	从 1 循环到 $n$：$O(n)$
空间复杂度	内存使用量（栈、堆、数据结构）	递归调用深度：$O(n)$

简单规则：

• 顺序步骤：成本求和
• 嵌套循环：规模相乘
• 递归：使用递推关系

常见模式

模式	成本公式	复杂度
单层循环（1 到 $n$）	$T(n) = n$	$O(n)$
嵌套循环（$n \times n$）	$T(n) = n^2$	$O(n^2)$
每次减半	$T(n) = \log_2 n$	$O(\log n)$
分治法（分成两半）	$T(n) = 2T(n/2)+n$	$O(n\log n)$

翻倍规则

用 $n$ 和 $2n$ 运行算法：

观察结果	可能的复杂度
时间恒定	$O(1)$
时间翻倍	$O(n)$
时间变为 4 倍	$O(n^2)$
时间乘以对数因子	$O(n\log n)$

微型代码：二分查找

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

复杂度： $$T(n) = T(n/2) + 1 \Rightarrow O(\log n)$$

常见陷阱

问题	提示
差一错误	仔细检查循环边界
无限循环	确保终止条件可达
中点溢出（C/C++）	使用 mid = lo + (hi - lo) / 2
在搜索中使用未排序的数据	二分查找仅适用于已排序的输入

增长率快速总结

类型	公式示例	描述
常数	$1$	固定时间
对数	$\log n$	每次减半
线性	$n$	遍历所有项
线性对数	$n \log n$	类似排序的复杂度
平方	$n^2$	双层循环
立方	$n^3$	三层嵌套循环
指数	$2^n$	所有子集
阶乘	$n!$	所有排列

简单经验法则

手动追踪小例子。 计算步数、内存使用和递归深度。 在运行代码之前，你就能看出增长趋势。

第 2 页：递归式与主定理

本页将帮助你分解递归算法，并使用递归式估算其运行时间。

什么是递归式？

递归关系式用更小的子问题的成本来表达问题成本 $T(n)$。

典型结构：

$$ T(n) = a T\left(\frac{n}{b}\right) + f(n) $$

其中：

• $a$ = 子问题的数量
• $b$ = 输入规模缩小的因子
• $f(n)$ = 每次调用额外的工作量（合并、组合等）

常见的递归式

算法	递归式形式	解
二分查找	$T(n)=T(n/2)+1$	$O(\log n)$
归并排序	$T(n)=2T(n/2)+n$	$O(n\log n)$
快速排序（平均）	$T(n)=2T(n/2)+O(n)$	$O(n\log n)$
快速排序（最坏）	$T(n)=T(n-1)+O(n)$	$O(n^2)$
矩阵乘法	$T(n)=8T(n/2)+O(n^2)$	$O(n^3)$
Karatsuba 算法	$T(n)=3T(n/2)+O(n)$	$O(n^{\log_2 3})$

求解递归式

有几种方法可以求解递归式：

方法	描述	最适用场景
迭代法	逐步展开	简单的递归式
代入法	猜测并用归纳法证明	验证
递归树法	可视化每一层的总工作量	分治算法
主定理	求解 $T(n)=aT(n/b)+f(n)$ 的捷径	标准形式

主定理

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

令 $$n^{\log_b a}$$ 为“临界项”

情况	条件	结果
1	如果 $f(n) = O(n^{\log_b a - \varepsilon})$	$T(n) = \Theta(n^{\log_b a})$
2	如果 $f(n) = \Theta(n^{\log_b a}\log^k n)$	$T(n) = \Theta(n^{\log_b a}\log^{k+1} n)$
3	如果 $f(n) = \Omega(n^{\log_b a + \varepsilon})$ 且满足正则条件	$T(n) = \Theta(f(n))$

示例

算法	$a$	$b$	$f(n)$	情况	$T(n)$
归并排序	2	2	$n$	2	$\Theta(n\log n)$
二分查找	1	2	$1$	1	$\Theta(\log n)$
Strassen 矩阵乘法	7	2	$n^2$	2	$\Theta(n^{\log_2 7})$
快速排序（平均）	2	2	$n$	2	$\Theta(n\log n)$

递归树可视化

将成本分解到各层：

示例：$T(n)=2T(n/2)+n$

层数	节点数	每个节点的工作量	总工作量
0	1	$n$	$n$
1	2	$n/2$	$n$
2	4	$n/4$	$n$
...	...	...	...

对 $\log_2 n$ 层求和：

$$T(n) = n \log_2 n$$

微型代码：快速幂运算

高效计算 $a^n$。

def power(a, n):
    res = 1
    while n > 0:
        if n % 2 == 1:
            res *= a
        a *= a
        n //= 2
    return res

递归式：

$$T(n) = T(n/2) + O(1) \Rightarrow O(\log n)$$

迭代法示例

求解 $T(n)=T(n/2)+n$

展开：

$$ \begin{aligned} T(n) &= T(n/2) + n \ &= T(n/4) + n/2 + n \ &= T(n/8) + n/4 + n/2 + n \ &= \ldots + n(1 + 1/2 + 1/4 + \ldots) \ &= O(n) \end{aligned} $$

常见形式

形式	结果
$T(n)=T(n-1)+O(1)$	$O(n)$
$T(n)=T(n/2)+O(1)$	$O(\log n)$
$T(n)=2T(n/2)+O(1)$	$O(n)$
$T(n)=2T(n/2)+O(n)$	$O(n\log n)$
$T(n)=T(n/2)+O(n)$	$O(n)$

快速检查清单

1. 识别 $a$、$b$ 和 $f(n)$
2. 比较 $f(n)$ 与 $n^{\log_b a}$
3. 应用正确的情况
4. 确认假设（正则条件）
5. 给出最终的复杂度

理解递归式有助于你在编码前估算性能。 始终关注子问题的数量、大小以及合并成本。

第 3 页：排序概览

排序是最常见的算法任务之一。本页帮助您快速比较各种排序方法、它们的复杂度、稳定性以及适用场景。

为什么排序很重要

排序可以组织数据，使搜索、合并和分析变得高效。 一旦输入数据被排序，许多问题就会变得更简单。

快速比较表

算法	最佳情况	平均情况	最坏情况	空间复杂度	稳定	原地	备注
冒泡排序	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	是	是	简单，适合教学
选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	否	是	交换次数少
插入排序	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	是	是	适用于小数据或部分有序数据
归并排序	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$	$O(n)$	是	否	稳定，分治策略
快速排序	$O(n\log n)$	$O(n\log n)$	$O(n^2)$	$O(\log n)$	否	是	平均速度快，原地排序
堆排序	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$	$O(1)$	否	是	不稳定
计数排序	$O(n+k)$	$O(n+k)$	$O(n+k)$	$O(n+k)$	是	否	仅适用于整数键
基数排序	$O(d(n+k))$	$O(d(n+k))$	$O(d(n+k))$	$O(n+k)$	是	否	按位排序
桶排序	$O(n+k)$	$O(n+k)$	$O(n^2)$	$O(n)$	是	否	需要数据均匀分布

如何选择排序算法

场景	最佳选择
小数组或接近有序的数据	插入排序
需要稳定排序，一般情况	归并排序或 Timsort
需要原地排序且平均速度快	快速排序
保证最坏情况 $O(n\log n)$	堆排序
小整数键或有限范围	计数排序或基数排序
外部排序（大数据）	外部归并排序

微型代码：插入排序

对初学者来说简单直观。

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

复杂度： $$T(n) = O(n^2)$$ 平均情况，$$O(n)$$ 最佳情况（已排序）

分治排序

归并排序

分割列表，排序子序列，合并结果。

递归式： $$T(n) = 2T(n/2) + O(n) = O(n\log n)$$

微型代码：

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a)//2
    L = merge_sort(a[:mid])
    R = merge_sort(a[mid:])
    i = j = 0
    res = []
    while i < len(L) and j < len(R):
        if L[i] <= R[j]:
            res.append(L[i]); i += 1
        else:
            res.append(R[j]); j += 1
    res.extend(L[i:]); res.extend(R[j:])
    return res

快速排序

选择枢轴，分区，排序子数组。

递归式： $$T(n) = T(k) + T(n-k-1) + O(n)$$ 平均情况：$$O(n\log n)$$ 最坏情况：$$O(n^2)$$

微型代码：

def quick_sort(a):
    if len(a) <= 1:
        return a
    pivot = a[len(a)//2]
    left  = [x for x in a if x < pivot]
    mid   = [x for x in a if x == pivot]
    right = [x for x in a if x > pivot]
    return quick_sort(left) + mid + quick_sort(right)

稳定排序 vs 不稳定排序

属性	描述	示例
稳定	相等元素保持原始顺序	归并排序，插入排序
不稳定	可能重排相等元素的顺序	快速排序，堆排序

可视化技巧

模式	描述
冒泡	比较并交换相邻元素
选择	每轮选择最小值
插入	逐步扩展有序区域
归并	分割，征服，合并
快速	分区并递归
堆	建堆，重复提取

总结表

类型	类别	复杂度	稳定	空间复杂度
简单排序	冒泡，选择	$O(n^2)$	视情况而定	$O(1)$
插入排序	增量式	$O(n^2)$	是	$O(1)$
分治排序	归并，快速	$O(n\log n)$	归并稳定	归并非原地
分布排序	计数，基数	$O(n+k)$	是	$O(n+k)$
混合排序	Timsort, IntroSort	$O(n\log n)$	是	视情况而定

如有疑问，可以从 Timsort（Python）或 std::sort（C++）开始，它们能动态适应。

第 4 页：搜索与选择

搜索意味着从集合中找到你需要的元素。选择意味着挑选特定的元素，例如最小、最大或第 k 个元素。本页对两者进行总结。

搜索基础

类型	描述	数据要求	复杂度
线性搜索	逐个检查	无	$O(n)$
二分搜索	每一步将范围除以 2	已排序	$O(\log n)$
跳跃搜索	向前跳过固定步数	已排序	$O(\sqrt n)$
插值搜索	基于值猜测位置	已排序，均匀分布	平均 $O(\log\log n)$
指数搜索	扩展窗口，然后二分搜索	已排序	$O(\log n)$

线性搜索

简单，但对于大型输入较慢。

def linear_search(a, x):
    for i, v in enumerate(a):
        if v == x:
            return i
    return -1

复杂度： $$T(n) = O(n)$$

二分搜索

在已排序列表上快速。

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

复杂度： $$T(n) = T(n/2) + 1 \Rightarrow O(\log n)$$

二分搜索变体

变体	目标	返回值
下界	第一个满足 $a[i] \ge x$ 的索引	第一个 ≥ x 的位置
上界	第一个满足 $a[i] > x$ 的索引	第一个 > x 的位置
计数范围	upper_bound - lower_bound	排序数组中 $x$ 的个数

常见的二分搜索陷阱

问题	修复方法
无限循环	正确更新边界
差一错误	仔细检查中间值的包含关系
不适用于未排序数据	排序或使用基于哈希的搜索
溢出（C/C++）	mid = lo + (hi - lo) / 2

指数搜索

用于无界或大型已排序列表。

1. 检查位置 $1, 2, 4, 8, ...$ 直到 $a[i] \ge x$
2. 在最后找到的区间内进行二分搜索

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

选择问题

查找第 $k$ 个最小或最大元素。

任务	示例用例	算法	复杂度
最小值 / 最大值	最小 / 最大元素	线性扫描	$O(n)$
第 k 小元素	顺序统计量	快速选择	平均 $O(n)$
中位数	中间元素	快速选择	平均 $O(n)$
前 k 个元素	部分排序	堆 / 分区	$O(n\log k)$
中位数的中位数	最坏情况线性选择	确定性算法	$O(n)$

微型代码：快速选择（第 k 小元素）

import random

def quickselect(a, k):
    if len(a) == 1:
        return a[0]
    pivot = random.choice(a)
    left  = [x for x in a if x < pivot]
    mid   = [x for x in a if x == pivot]
    right = [x for x in a if x > pivot]

    if k < len(left):
        return quickselect(left, k)
    elif k < len(left) + len(mid):
        return pivot
    else:
        return quickselect(right, k - len(left) - len(mid))

复杂度： 平均 $O(n)$，最坏 $O(n^2)$

微型代码：下界

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

基于哈希的搜索

当顺序无关紧要时，哈希提供接近常数的查找时间。

操作	平均	最坏
插入	$O(1)$	$O(n)$
搜索	$O(1)$	$O(n)$
删除	$O(1)$	$O(n)$

最适合大型、未排序的集合。

总结表

场景	推荐方法	复杂度
小型数组	线性搜索	$O(n)$
大型、已排序数组	二分搜索	$O(\log n)$
无界范围	指数搜索	$O(\log n)$
需要第 k 小元素	快速选择	平均 $O(n)$
多次查找	哈希表	平均 $O(1)$

快速提示

• 在应用二分搜索之前，始终检查数据是否已排序。
• 当你只需要第 k 个元素，而不是完全排序时，快速选择非常有用。
• 对未排序数据使用哈希映射进行快速查找。

第 5 页：核心数据结构

数据结构组织数据以实现高效的访问和修改。 选择合适的数据结构常常能使算法变得简单而快速。

数组和列表

结构	访问	查找	尾部插入	中间插入	删除	备注
静态数组	$O(1)$	$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(1)$	顺序访问
双向链表	$O(n)$	$O(n)$	头部/尾部 $O(1)$	已知节点时 $O(1)$	已知节点时 $O(1)$	双向遍历

• 单向链表：仅有 next 指针
• 双向链表：有 next 和 prev 指针
• 动态数组使用倍增策略来增加容量

微型代码：动态数组扩容（类 Python）

def resize(arr, new_cap):
    new = [None] * new_cap
    for i in range(len(arr)):
        new[i] = arr[i]
    return new

容量倍增策略使得尾部追加操作保持均摊 $O(1)$ 复杂度。

栈和队列

结构	入栈/入队	出栈/出队	查看顶部/队首	备注
栈 (LIFO)	$O(1)$	$O(1)$	$O(1)$	撤销操作，递归
队列 (FIFO)	$O(1)$	$O(1)$	$O(1)$	调度，广度优先搜索
双端队列	$O(1)$	$O(1)$	$O(1)$	可在两端插入/删除

微型代码：栈

stack = []
stack.append(x)   # 入栈
x = stack.pop()   # 出栈

微型代码：队列

from collections import deque

q = deque()
q.append(x)   # 入队
x = q.popleft()  # 出队

优先队列（堆）

存储元素，使得最小（或最大）的元素始终位于顶部。

操作	复杂度
插入	$O(\log n)$
提取最小值	$O(\log n)$
查看最小值	$O(1)$
建堆	$O(n)$

微型代码：

import heapq
heap = []
heapq.heappush(heap, value)
x = heapq.heappop(heap)

堆用于 Dijkstra（迪杰斯特拉）算法、Prim（普里姆）算法和调度问题。

哈希表

操作	平均情况	最坏情况	备注
插入	$O(1)$	$O(n)$	哈希冲突会增加开销
查找	$O(1)$	$O(n)$	良好的哈希函数和低负载因子有帮助
删除	$O(1)$	$O(n)$	通常使用开放寻址或链地址法

核心思想：

• 使用哈希函数计算索引：index = hash(key) % capacity
• 通过链地址法或开放寻址法解决冲突

微型代码：哈希映射（简化版）

table = [[] for _ in range(8)]
def put(key, value):
    i = hash(key) % len(table)
    for kv in table[i]:
        if kv[0] == key:
            kv[1] = value
            return
    table[i].append([key, value])

集合

基于哈希的唯一元素集合。

操作	平均复杂度
添加	$O(1)$
查找	$O(1)$
删除	$O(1)$

用于成员检查和去重。

并查集（不相交集）

跟踪连通分量。 两个主要操作：

• find(x)：获取 x 的代表元素
• union(a, b)：合并 a 和 b 所在的集合

配合路径压缩和按秩合并 → 接近 $O(1)$。

微型代码：

class DSU:
    def __init__(self, n):
        self.p = list(range(n))
        self.r = [0]*n
    def find(self, x):
        if self.p[x] != x:
            self.p[x] = self.find(self.p[x])
        return self.p[x]
    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb: return
        if self.r[ra] < self.r[rb]: ra, rb = rb, ra
        self.p[rb] = ra
        if self.r[ra] == self.r[rb]:
            self.r[ra] += 1

总结表格

类别	结构	使用场景
序列	数组，列表	有序数据
LIFO/FIFO	栈，队列	递归，调度
优先级	堆	最佳优先选择，优先队列问题
基于哈希	哈希表，集合	快速查找，唯一性
连通性	并查集	图连通分量，聚类

快速提示

• 当随机访问重要时，选择数组。
• 当频繁插入/删除时，选择链表。
• 为控制流选择栈或队列。
• 为优先级选择堆。
• 为常量时间查找选择哈希表。
• 为不相交集或图合并选择并查集。

第 6 页：图算法速查

图用于建模对象之间的连接关系。 它们无处不在：地图、网络、依赖关系和系统中。 本页为您提供了常见图算法的简明概览。

图基础

图由顶点（节点）和边（连接）组成。

类型	描述
无向图	边是双向的
有向图	边具有方向
加权图	边带有成本或距离
无权图	所有边的成本为 1

表示方法

表示方法	空间复杂度	最适合	备注
邻接表	$O(V+E)$	稀疏图	实践中常用
邻接矩阵	$O(V^2)$	稠密图	常数时间查找边
边列表	$O(E)$	基于边的算法	易于遍历边

邻接表示例（Python）：

graph = {
    0: [(1, 2), (2, 5)],
    1: [(2, 1)],
    2: []
}

每个元组 (neighbor, weight) 代表一条边。

遍历

广度优先搜索（BFS）

逐层访问（适用于无权图中的最短路径）。

from collections import deque
def bfs(adj, s):
    dist = {s: 0}
    q = deque([s])
    while q:
        u = q.popleft()
        for v in adj[u]:
            if v not in dist:
                dist[v] = dist[u] + 1
                q.append(v)
    return dist

复杂度：$O(V+E)$

深度优先搜索（DFS）

在回溯之前深入探索。

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

复杂度：$O(V+E)$

最短路径算法

算法	适用图类型	允许负权边？	复杂度	备注
BFS	无权图	否	$O(V+E)$	最短跳数
Dijkstra	加权图（非负权）	否	$O((V+E)\log V)$	使用优先队列
Bellman-Ford	加权图	是	$O(VE)$	可检测负权环
Floyd-Warshall	所有节点对	是	$O(V^3)$	动态规划方法

精简代码：Dijkstra 算法

import heapq

def dijkstra(adj, s):
    INF = 1018
    dist = [INF] * len(adj)
    dist[s] = 0
    pq = [(0, s)]
    while pq:
        d, u = heapq.heappop(pq)
        if d != dist[u]: 
            continue
        for v, w in adj[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist

拓扑排序（仅适用于有向无环图）

对节点排序，使得每条边 $(u,v)$ 都从较早的节点指向较晚的节点。

方法	思路	复杂度
基于 DFS	后序栈反转	$O(V+E)$
Kahn 算法	移除入度为 0 的节点	$O(V+E)$

最小生成树（MST）

以最小的总权重连接所有节点。

算法	思路	复杂度	备注
Kruskal	对边排序，使用并查集	$O(E\log E)$	与边列表配合良好
Prim	使用优先队列生长树	$O(E\log V)$	可从任意顶点开始

精简代码：Kruskal MST

def kruskal(edges, n):
    parent = list(range(n))
    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]
    res = 0
    for w, u, v in sorted(edges):
        ru, rv = find(u), find(v)
        if ru != rv:
            res += w
            parent[rv] = ru
    return res

强连通分量（SCC）

子集中的每个节点都可以到达其他所有节点。 使用 Kosaraju 或 Tarjan 算法，两者复杂度均为 $O(V+E)$。

环检测

图类型	方法	备注
无向图	带父节点信息的 DFS	访问到非父节点的已访问边
有向图	带颜色/状态的 DFS	发现回边即存在环

总结表

任务	算法	复杂度	备注
访问所有节点	DFS / BFS	$O(V+E)$	遍历
最短路径（无权图）	BFS	$O(V+E)$	计算边数
最短路径（加权图）	Dijkstra	$O(E\log V)$	不允许负权
允许负权边	Bellman-Ford	$O(VE)$	可检测负权环
所有节点对最短路径	Floyd-Warshall	$O(V^3)$	动态规划矩阵
最小生成树	Kruskal / Prim	$O(E\log V)$	最小连接成本
有向无环图排序	拓扑排序	$O(V+E)$	仅适用于有向无环图

快速提示

• 在无权图中寻找最短路径时使用 BFS。
• 如果权重非负，使用 Dijkstra。
• 在 Kruskal MST 中使用并查集。
• 解决依赖关系时使用拓扑排序。
• 在使用 Dijkstra 之前，务必检查是否存在负权边。

第 7 页：动态规划快速使用指南

动态规划（DP）的核心思想是将大问题分解为重叠的子问题，并重用子问题的解。本页旨在帮助你快速识别动态规划的模式。

何时使用动态规划

通常，如果问题具备以下特征，就可以应用动态规划：

特征	含义
最优子结构	最优解由子问题的最优解构成
重叠子问题	相同的子结果会重复出现
决策 + 递推关系	可以定义状态之间的转移关系

动态规划的实现方式

方式	描述	示例
自顶向下（记忆化）	递归 + 缓存结果	带记忆化的斐波那契数列
自底向上（表格法）	迭代填充表格	背包问题的表格解法
空间优化	复用前一行/前一个状态	滚动数组

斐波那契数列示例

递推关系： $$F(n)=F(n-1)+F(n-2),\quad F(0)=0,F(1)=1$$

自顶向下（记忆化）

def fib(n, memo={}):
    if n <= 1:
        return n
    if n not in memo:
        memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]

自底向上（表格法）

def fib(n):
    dp = [0, 1]
    for i in range(2, n + 1):
        dp.append(dp[i-1] + dp[i-2])
    return dp[n]

解决动态规划问题的步骤

1. 定义状态 示例：$dp[i]$ = 前 $i$ 个物品的最优解
2. 定义状态转移方程 示例：$dp[i]=\max(dp[i-1], value[i]+dp[i-weight[i]])$
3. 设置基本情况 示例：$dp[0]=0$
4. 选择计算顺序 自底向上或自顶向下
5. 返回答案 通常是 $dp[n]$ 或 $dp[target]$

常见的动态规划类别

类别	示例问题	状态形式
序列	最长递增子序列，最长公共子序列，编辑距离	$dp[i][j]$ 基于前缀
子集	背包问题，子集和问题	$dp[i][w]$ 基于容量
划分	回文划分，等和子集	$dp[i]$ 基于切割点
网格	最小路径和，不同路径	$dp[i][j]$ 基于单元格
计数	零钱兑换（组合数），爬楼梯	从子问题累加方案数
区间	矩阵链乘法，戳气球	$dp[i][j]$ 基于区间子问题
状态压缩	旅行商问题，任务分配	$dp[mask][i]$ 基于子集状态
数位	满足约束的数字计数	$dp[pos][tight][sum]$ 基于数位
树形	换根动态规划，子树动态规划	$dp[u]$ 基于子节点

经典问题

问题	状态定义	状态转移方程
爬楼梯	$dp[i]=$ 到达第 i 级台阶的方法数	$dp[i]=dp[i-1]+dp[i-2]$
零钱兑换（组合数）	$dp[x]=$ 组成金额 x 的方法数	$dp[x]+=dp[x-coin]$
0/1 背包	$dp[w]=$ 重量不超过 w 的最大价值	$dp[w]=\max(dp[w],dp[w-w_i]+v_i)$
最长递增子序列	$dp[i]=$ 以 i 结尾的最长递增子序列长度	若 $a[j]<a[i]$，则 $dp[i]=dp[j]+1$
编辑距离	$dp[i][j]=$ 编辑代价	min(插入，删除，替换)
矩阵链乘法	$dp[i][j]=$ 子链相乘的最小代价	$dp[i][j]=\min_k(dp[i][k]+dp[k+1][j])$

精简代码：0/1 背包（一维空间优化）

def knapsack(weights, values, W):
    dp = [0]*(W+1)
    for i in range(len(weights)):
        for w in range(W, weights[i]-1, -1):
            dp[w] = max(dp[w], dp[w-weights[i]] + values[i])
    return dp[W]

序列对齐示例

编辑距离递推关系：

$$ dp[i][j] = \begin{cases} dp[i-1][j-1], & \text{if } s[i] = t[j],\ 1 + \min(dp[i-1][j],\ dp[i][j-1],\ dp[i-1][j-1]), & \text{otherwise.} \end{cases} $$

优化技巧

技巧	适用场景	示例
空间优化	二维状态可复用为一维	背包问题，最长公共子序列
前缀/后缀预处理	区间聚合查询	区间和/最小值查询
分治动态规划	决策具有单调性	矩阵链乘法
凸包优化	转移方程为线性函数取最小值	基于直线的动态规划
位集动态规划	状态为大规模布尔集合	子集和问题的优化

调试技巧

• 打印部分 dp 数组以观察计算过程。
• 仔细检查基本情况。
• 确保循环顺序符合状态转移的依赖关系。
• 在编码之前，务必确认递推关系是正确的。

第 8 页：算法快速数学指南

数学为算法推理奠定了基础。 本页汇集了每个程序员都应该了解的基本公式和方法。

数论基础

主题	描述	公式 / 思路
最大公约数（欧几里得算法）	最大公约数	$\gcd(a, b) = \gcd(b, a \bmod b)$
扩展欧几里得算法	求解 $ax+by=gcd(a,b)$	回溯系数
最小公倍数	最小公倍数	$lcm(a,b)=\frac{a\cdot b}{gcd(a,b)}$
模加法	模 M 下的加法	$(a+b)\bmod M$
模乘法	模 M 下的乘法	$(a\cdot b)\bmod M$
模逆元	$a^{-1}\bmod M$	若 M 为质数，则 $a^{M-2}\bmod M$
模幂运算	快速幂运算	平方乘算法
中国剩余定理	合并同余式	求解方程组 $x\equiv a_i\pmod{m_i}$

微型代码（模幂运算）：

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

素数与因数分解

算法	用例	复杂度	备注
试除法	小 n	$O(\sqrt{n})$	简单
埃拉托斯特尼筛法	生成素数	$O(n\log\log n)$	经典素数筛法
米勒-拉宾算法	概率性素数测试	$O(k\log^3 n)$	对大 n 快速
Pollard Rho 算法	分解合数	$O(n^{1/4})$	随机化算法
Atkin 筛法	更快的变体	$O(n)$	实现复杂

组合数学

公式	描述
$n! = n\cdot(n-1)\cdots1$	阶乘
$\binom{n}{k}=\dfrac{n!}{k!(n-k)!}$	组合数
$P(n,k)=\dfrac{n!}{(n-k)!}$	排列数
帕斯卡法则：$\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}$	构建帕斯卡三角形
卡特兰数：$C_n=\dfrac{1}{n+1}\binom{2n}{n}$	括号计数

微型代码（使用阶乘和逆元计算 nCr 模 M）：

def nCr(n, r, fact, inv):
    return fact[n]*inv[r]%M*inv[n-r]%M

概率基础

概念	公式或思路
概率	$P(A)=\frac{\text{有利情况}}{\text{总情况}}$
补集	$P(\bar{A})=1-P(A)$
并集	$P(A\cup B)=P(A)+P(B)-P(A\cap B)$
条件概率	$P(A \mid B)=\frac{P(A\cap B)}{P(B)}$
贝叶斯定理	$P(A \mid B)=\frac{P(B \mid A)P(A)}{P(B)}$
期望值	$E[X]=\sum x_iP(x_i)$
方差	$Var(X)=E[X^2]-E[X]^2$

线性代数核心

运算	公式 / 方法	复杂度
高斯消元法	求解 $Ax=b$	$O(n^3)$
行列式	主元的乘积	$O(n^3)$
矩阵乘法	$(AB)_{ij}=\sum_k A_{ik}B_{kj}$	$O(n^3)$
转置	$A^T_{ij}=A_{ji}$	$O(n^2)$
LU 分解	$A=LU$（下三角，上三角）	$O(n^3)$
Cholesky 分解	$A=LL^T$（对称正定）	$O(n^3)$
幂法	主特征值估计	迭代

微型代码（高斯消元法框架）：

for i in range(n):
    pivot = a[i][i]
    for j in range(i, n+1):
        a[i][j] /= pivot
    for k in range(n):
        if k != i:
            ratio = a[k][i]
            for j in range(i, n+1):
                a[k][j] -= ratio*a[i][j]

快速变换

变换	用例	复杂度	备注
快速傅里叶变换	多项式卷积	$O(n\log n)$	复数
数论变换	模卷积	$O(n\log n)$	素数模数
快速沃尔什变换（异或）	基于异或的卷积	$O(n\log n)$	子集动态规划

FFT 公式：

$$ X_k = \sum_{n=0}^{N-1} x_n e^{-2\pi i kn/N} $$

数值方法

方法	目的	公式或思路
二分法	求根	中点二分直到 $f(x)=0$
牛顿-拉夫森法	快速收敛	$x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}$
割线法	近似导数	$x_{n+1}=x_n-f(x_n)\frac{x_n-x_{n-1}}{f(x_n)-f(x_{n-1})}$
辛普森法则	积分	$\int_a^bf(x)dx\approx\frac{h}{3}(f(a)+4f(m)+f(b))$

优化与微积分

概念	公式 / 思路
导数	$f'(x)=\lim_{h\to0}\frac{f(x+h)-f(x)}{h}$
梯度下降	$x_{k+1}=x_k-\eta\nabla f(x_k)$
拉格朗日乘数法	$\nabla f=\lambda\nabla g$
凸函数	$f(\lambda x+(1-\lambda)y)\le\lambda f(x)+(1-\lambda)f(y)$

微型代码（梯度下降）：

x = x0
for _ in range(1000):
    grad = df(x)
    x -= lr * grad

代数技巧

主题	公式 / 用途
幂运算	通过平方乘算法计算 $a^n$
多项式求导	$(ax^n)' = n\cdot a x^{n-1}$
积分	$\int x^n dx = \frac{x^{n+1}}{n+1}+C$
莫比乌斯反演	$f(n)=\sum_{d \mid n}g(d)\implies g(n)=\sum_{d \mid n}\mu(d)\cdot f(n/d)$

快速参考表

领域	必须掌握的算法
数论	最大公约数，模幂运算，中国剩余定理
组合数学	帕斯卡法则，阶乘，卡特兰数
概率	贝叶斯定理，期望值
线性代数	高斯消元法
变换	快速傅里叶变换，数论变换
优化	梯度下降

第 9 页：字符串与文本算法速查

字符串是用于文本搜索、匹配和转换的字符序列。 本页提供了经典和现代字符串技术的快速参考。

字符串基础

概念	描述	示例
字母表	符号的集合	{a, b, c}
字符串长度	字符的数量	"hello" → 5
子串	字符串的连续部分	"ell" 在 "hello" 中
子序列	有序子集（不一定连续）	"hlo" 来自 "hello"
前缀 / 后缀	字符串的起始 / 结尾部分	"he", "lo"

索引：大多数算法使用从 0 开始的索引。

字符串搜索概述

算法	复杂度	描述
朴素搜索	$O(nm)$	检查所有位置
KMP	$O(n+m)$	前缀-后缀跳转表
Z 算法	$O(n+m)$	预计算匹配长度
Rabin–Karp	$O(n+m)$ 平均	滚动哈希检查
Boyer–Moore	$O(n/m)$ 平均	反向扫描，跳过不匹配

KMP 前缀函数

为模式计算前缀-后缀匹配。

步骤	含义
$pi[i]$	对于 $pattern[0:i]$，同时也是其后缀的最长真前缀的长度

微型代码：

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

搜索时使用 pi 来跳过不匹配。

Z 算法

计算从位置 i 开始的子串与模式前缀匹配的最长长度。

步骤	含义
$Z[i]$	从 i 开始的最长与模式前缀匹配的子串的长度

使用 $S = pattern + '$' + text$ 来查找模式出现的位置。

Rabin–Karp 滚动哈希

思路	计算文本窗口的哈希值，滑动窗口，进行比较

哈希函数： $$ h(s) = (s_0p^{n-1} + s_1p^{n-2} + \dots + s_{n-1}) \bmod M $$

滑动一个字符时高效地更新哈希值。

微型代码：

def rolling_hash(s, base=257, mod=109+7):
    h = 0
    for ch in s:
        h = (h*base + ord(ch)) % mod
    return h

高级模式匹配

算法	使用场景	复杂度
Boyer–Moore	大字母表	$O(n/m)$ 平均
Sunday	最后字符移位启发式	$O(n)$ 平均
Bitap	近似匹配	$O(nm/w)$
Aho–Corasick	多模式搜索	$O(n+z)$

Aho–Corasick 自动机

从模式构建字典树并计算失败链接。

步骤	描述
构建字典树	添加所有模式
失败链接	回退到下一个前缀
输出链接	记录模式匹配

微型代码框架：

from collections import deque

def build_ac(patterns):
    trie = [{}]
    fail = [0]
    for pat in patterns:
        node = 0
        for c in pat:
            node = trie[node].setdefault(c, len(trie))
            if node == len(trie):
                trie.append({})
                fail.append(0)
    # 计算失败链接
    q = deque()
    for c in trie[0]:
        q.append(trie[0][c])
    while q:
        u = q.popleft()
        for c, v in trie[u].items():
            f = fail[u]
            while f and c not in trie[f]:
                f = fail[f]
            fail[v] = trie[f].get(c, 0)
            q.append(v)
    return trie, fail

后缀结构

结构	用途	构建时间
后缀数组	后缀索引的排序列表	$O(n\log n)$
LCP 数组	后缀的最长公共前缀	$O(n)$
后缀树	后缀的字典树	$O(n)$ (Ukkonen)
后缀自动机	子串的最小确定性有限自动机	$O(n)$

后缀数组倍增法：

• 对长度为 $2^k$ 的子串进行排名
• 使用排名对进行排序和合并

通过 Kasai 算法计算 LCP： $$ LCP[i]=\text{后缀 } S[SA[i]:] \text{ 和 } S[SA[i-1]:] \text{ 的公共前缀长度} $$

回文检测

算法	描述	复杂度
Manacher 算法	最长回文子串	$O(n)$
动态规划表	检查子串是否为回文	$O(n^2)$
中心扩展	围绕中心扩展	$O(n^2)$

Manacher 算法核心：

• 使用分隔符（#）进行转换
• 跟踪每个中心周围回文的半径

编辑距离系列

算法	描述	复杂度
Levenshtein 距离	插入/删除/替换	$O(nm)$
Damerau–Levenshtein	增加相邻字符交换	$O(nm)$
Hirschberg	空间优化的 LCS	$O(nm)$ 时间，$O(n)$ 空间

递推关系： $$ dp[i][j]=\min \begin{cases} dp[i-1][j]+1 \ dp[i][j-1]+1 \ dp[i-1][j-1]+(s_i\neq t_j) \end{cases} $$

压缩技术

算法	类型	思路
Huffman 编码	前缀码	为高频字符分配更短的码字
算术编码	范围编码	分数区间表示
LZ77 / LZ78	基于字典	重用先前的子串
BWT + MTF + RLE	块排序	在编码前将相似字符分组

Huffman 原理： 为频率更高的符号分配更短的比特串。

哈希与校验和

算法	使用场景	备注
CRC32	错误检测	简单的多项式取模
MD5	哈希（旧版）	不安全
SHA-256	安全哈希	加密用途
滚动哈希	子串比较	用于 Rabin–Karp

快速参考

任务	算法	复杂度
单模式搜索	KMP / Z	$O(n+m)$
多模式搜索	Aho–Corasick	$O(n+z)$
近似搜索	Bitap / Wu–Manber	$O(kn)$
子串查询	后缀数组 + LCP	$O(\log n)$
回文	Manacher	$O(n)$
压缩	Huffman / LZ77	可变
编辑距离	动态规划表	$O(nm)$

第 10 页：几何、图形与空间算法速查

几何帮助我们解决关于形状、距离和空间关系的问题。 本页通过简单的公式和示例总结了核心的计算几何技术。

坐标基础

概念	描述	公式 / 示例
点距离	$(x_1,y_1)$ 和 $(x_2,y_2)$ 之间的距离	$d=\sqrt{(x_2-x_1)^2+(y_2-y_1)^2}$
中点	两点之间	$(\frac{x_1+x_2}{2}, \frac{y_1+y_2}{2})$
点积	角度与投影	$\vec{a}\cdot\vec{b}= \Vert\vec{a}\Vert \Vert\vec{b}\Vert \cos\theta$
叉积 (2D)	有向面积，方向判定	$a\times b = a_xb_y - a_yb_x$
方向测试	逆时针、顺时针、共线检查	$\text{sign}(a\times b)$

微型代码 (方向测试):

def orient(a, b, c):
    val = (b[0]-a[0])*(c[1]-a[1]) - (b[1]-a[1])*(c[0]-a[0])
    return 0 if val == 0 else (1 if val > 0 else -1)

凸包

寻找包含所有点的最小凸多边形。

算法	复杂度	备注
Graham Scan	$O(n\log n)$	按角度排序，使用栈
Andrew's Monotone	$O(n\log n)$	按 x 排序，构建上/下包
Jarvis March	$O(nh)$	包裹法，h = 凸包大小
Chan's Algorithm	$O(n\log h)$	输出敏感的凸包算法

步骤:

1. 对点排序
2. 构建下凸包
3. 构建上凸包
4. 连接

最近点对

分治法。

步骤	描述
按 x 分割	将点分成两半
递归与合并	跟踪跨越条带的最小距离

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

公式: $$ d(p,q)=\sqrt{(x_p-x_q)^2+(y_p-y_q)^2} $$

线段相交

两条线段 $(p_1,p_2)$ 和 $(q_1,q_2)$ 相交的条件是:

1. 方向测试结果不同
2. 如果共线，则线段在直线上有重叠

微型代码:

def intersect(p1, p2, q1, q2):
    o1 = orient(p1, p2, q1)
    o2 = orient(p1, p2, q2)
    o3 = orient(q1, q2, p1)
    o4 = orient(q1, q2, p2)
    return o1 != o2 and o3 != o4

多边形面积 (鞋带公式)

对于按顺序排列的顶点 $(x_i, y_i)$:

$$ A=\frac{1}{2}\left|\sum_{i=0}^{n-1}(x_iy_{i+1}-x_{i+1}y_i)\right| $$

微型代码:

def area(poly):
    s = 0
    n = len(poly)
    for i in range(n):
        x1, y1 = poly[i]
        x2, y2 = poly[(i+1)%n]
        s += x1*y2 - x2*y1
    return abs(s)/2

点是否在多边形内

方法	思路	复杂度
射线法	计算边交叉次数	$O(n)$
环绕数法	跟踪有向旋转次数	$O(n)$
凸多边形测试	检查所有方向	$O(n)$

射线法: 交叉次数为奇数 → 在内部。

旋转卡尺

用于:

• 多边形直径 (最远点对)
• 最小包围矩形
• 宽度与对跖点对

思路: 使用切线围绕凸包扫描。 复杂度: 构建凸包后为 $O(n)$。

扫描线技术

问题	方法	复杂度
最近点对	按 y 维护活动集	$O(n\log n)$
线段相交	基于事件的扫描	$O((n+k)\log n)$
矩形并集面积	垂直边事件	$O(n\log n)$
天际线问题	按高度合并	$O(n\log n)$

使用平衡树或优先队列维护活动集。

圆几何

概念	公式
方程	$(x-x_c)^2+(y-y_c)^2=r^2$
切线长度	$\sqrt{d^2-r^2}$
两圆相交	基于距离的几何

空间数据结构

结构	用途	备注
KD-Tree	最近邻搜索	轴对齐分割
R-Tree	范围查询	包围盒层次结构
Quadtree	2D 递归细分	图形学，碰撞检测
Octree	3D 扩展	体积划分
BSP Tree	平面分割	渲染，碰撞

光栅化与图形学

算法	目的	备注
Bresenham 直线	在整数网格上绘制直线	无需浮点数
中点画圆	圆的光栅化	利用对称性
扫描线填充	多边形填充算法	对边排序，水平扫描
Z-Buffer	隐藏面消除	逐像素深度比较
Phong 着色	平滑光照	插值法向量

空间路径规划

算法	描述	备注
A*	启发式最短路径	$f(n)=g(n)+h(n)$
Theta*	任意角度路径	基于捷径
RRT / RRT*	随机探索	机器人规划
PRM	概率路线图	采样图
可见性图	连接可见点	几何规划

快速总结

任务	算法	复杂度
凸包	Graham / Andrew	$O(n\log n)$
最近点对	分治法	$O(n\log n)$
线段相交检测	扫描线	$O(n\log n)$
点是否在多边形内	射线法	$O(n)$
多边形面积	鞋带公式	$O(n)$
最近邻搜索	KD-Tree	$O(\log n)$
路径规划	A*	$O(E\log V)$

提示

• 几何预处理时，总是先对点排序。
• 使用叉积进行方向测试。
• 尽可能使用整数运算以避免浮点误差。

第 11 页：系统、数据库与分布式算法速查

系统和数据库依赖于管理内存、并发、持久性和协调性的算法。本页概述了其中最重要的部分。

并发控制

确保多个事务或线程同时运行时保持正确性。

方法	核心思想	备注
两阶段锁 (2PL)	先获取锁，提交后再释放	保证可串行化
严格两阶段锁	持有所有锁直到提交	防止级联中止
保守两阶段锁	执行前锁定所有所需资源	无死锁但并行度较低
时间戳排序	按时间戳排序	可能中止较晚的事务
多版本并发控制 (MVCC)	读取者获取快照	用于 PostgreSQL, InnoDB
乐观并发控制 (OCC)	提交时验证	适用于低冲突工作负载

微型代码：时间戳排序

# 简化版
if write_ts[x] > txn_ts or read_ts[x] > txn_ts:
    abort()
else:
    write_ts[x] = txn_ts

每个对象跟踪其读时间戳和写时间戳。

死锁

事务间形成循环等待。

检测	构建等待图，检测环
预防	Wait-Die（老等少） / Wound-Wait（少中止）

检测复杂度：$O(V+E)$

微型代码（等待图环检测）：

def has_cycle(graph):
    visited, stack = set(), set()
    def dfs(u):
        visited.add(u)
        stack.add(u)
        for v in graph[u]:
            if v not in visited and dfs(v): return True
            if v in stack: return True
        stack.remove(u)
        return False
    return any(dfs(u) for u in graph)

日志与恢复

技术	描述	备注
预写日志	数据写入前先写日志	确保持久性
ARIES	分析、重做、撤销三阶段	行业标准
检查点	保存一致性快照	加速恢复
影子分页	写时复制更新	简单但灵活性较差

崩溃后恢复步骤：

1. 分析：找出活跃事务
2. 重做：重新应用已提交的更改
3. 撤销：回滚未提交的更改

索引

加速查找和范围查询。

索引类型	描述	备注
B-树 / B+树	平衡多路树	适合磁盘存储
哈希索引	仅支持精确匹配	不支持范围查询
GiST / R-树	空间数据	边界框层次结构
倒排索引	文本搜索	将词项映射到文档列表

B+树复杂度：$O(\log_B N)$ (B = 分支因子)

微型代码（索引中的二分查找）：

def search(node, key):
    i = bisect_left(node.keys, key)
    if i < len(node.keys) and node.keys[i] == key:
        return node.values[i]
    if node.is_leaf:
        return None
    return search(node.children[i], key)

查询处理

步骤	描述
解析	构建抽象语法树
优化	重排连接，选择索引
执行计划	为每个操作符选择算法
执行	评估迭代器或流水线

常见连接策略：

连接类型	复杂度	备注
嵌套循环连接	$O(nm)$	简单，慢
哈希连接	$O(n+m)$	构建 + 探测
排序合并连接	$O(n\log n+m\log m)$	输入已排序

缓存与替换策略

策略	描述	备注
LRU	驱逐最近最少使用项	简单，利用时间局部性
LFU	驱逐最不经常使用项	适用于稳定模式
ARC / LIRS	自适应混合策略	处理混合工作负载
随机	随机驱逐	简单，公平

微型代码（使用 OrderedDict 实现 LRU）：

from collections import OrderedDict

class LRU:
    def __init__(self, cap):
        self.cap = cap
        self.cache = OrderedDict()
    def get(self, k):
        if k not in self.cache: return -1
        self.cache.move_to_end(k)
        return self.cache[k]
    def put(self, k, v):
        if k in self.cache: self.cache.move_to_end(k)
        self.cache[k] = v
        if len(self.cache) > self.cap: self.cache.popitem(last=False)

分布式系统核心

问题	描述	典型解决方案
共识	跨节点就某个值达成一致	Paxos, Raft
领导者选举	选取协调者	Bully, Raft
复制	维护副本	日志复制
分区	拆分数据	一致性哈希
成员关系	检测节点	Gossip 协议

Raft 共识算法（简化版）

阶段	动作
选举	节点投票，选举领导者
复制	领导者追加日志条目
提交	一旦多数节点确认

安全性：已提交的条目永不改变。 活性：故障时选举出新领导者。

微型代码草图：

if vote_request.term > term:
    term = vote_request.term
    voted_for = candidate

一致性哈希

平滑地将键分布到节点上。

步骤	描述
将每个节点哈希到环上	例如 hash(node_id)
哈希每个键	找到顺时针方向的下一个节点
添加/删除节点	仅移动附近键

用于：Dynamo, Cassandra, Memcached。

容错模式

模式	描述	示例
复制	多个副本	主备复制
检查点	定期保存进度	机器学习训练
心跳	活性检测	集群管理器
重试 + 退避	处理瞬时故障	API 调用
法定读写	需要多数节点同意	Cassandra

分布式协调

工具 / 协议	描述	示例用途
ZooKeeper	集中式协调	锁，配置管理
Raft	分布式共识	日志复制
Etcd	基于 Raft 的键值存储	集群元数据

总结表

主题	算法 / 概念	复杂度	备注
锁	2PL, MVCC, OCC	可变	事务隔离
死锁	Wait-Die, 检测	$O(V+E)$	基于图的检查
恢复	ARIES, WAL	可变	崩溃恢复
索引	B+树, 哈希索引	$O(\log N)$	加速查询
连接	哈希 / 排序合并	可变	查询优化
缓存	LRU, LFU	$O(1)$	数据局部性
共识	Raft, Paxos	$O(n)$ 消息	容错
分区	一致性哈希	$O(1)$ 平均	可扩展性

快速提示

• 在并发中始终确保可串行化。
• 对于读密集型工作负载，使用 MVCC。
• ARIES 通过 WAL 确保持久性。
• 为了可扩展性，明智地进行分区和复制。
• 共识对于共享状态的正确性是必需的。

第 12 页：AI、ML 与优化算法速查

本页汇集了驱动现代人工智能和机器学习系统的经典算法，涵盖从聚类和分类到基于梯度的学习和元启发式方法。

经典机器学习算法

类别	算法	核心思想	复杂度
聚类	k-Means	分配到最近的质心，更新中心点	$O(nkt)$
聚类	k-Medoids (PAM)	以代表性点作为中心点	$O(k(n-k)^2)$
聚类	高斯混合模型 (EM)	通过概率进行软分配	每次迭代 $O(nkd)$
分类	朴素贝叶斯	在特征独立的假设下应用贝叶斯规则	$O(nd)$
分类	逻辑回归	线性 + sigmoid 激活函数	$O(nd)$
分类	SVM（线性）	通过凸优化最大化间隔	约 $O(nd)$
分类	k-NN	基于最近邻投票	每次查询 $O(nd)$
树	决策树 (CART)	通过不纯度递归分割	$O(nd\log n)$
投影	LDA / PCA	寻找最大化方差或类间分离度的投影	$O(d^3)$

微型代码：k-Means

import random, math

def kmeans(points, k, iters=100):
    # 随机选择 k 个点作为初始质心
    centroids = random.sample(points, k)
    for _ in range(iters):
        # 为每个质心创建分组
        groups = [[] for _ in range(k)]
        for p in points:
            # 找到距离最近的质心索引
            idx = min(range(k), key=lambda i: (p[0]-centroids[i][0])**2 + (p[1]-centroids[i][1])**2)
            groups[idx].append(p)
        new_centroids = []
        for g in groups:
            if g:
                # 计算新质心作为组内点的平均值
                x = sum(p[0] for p in g)/len(g)
                y = sum(p[1] for p in g)/len(g)
                new_centroids.append((x,y))
            else:
                # 如果分组为空，则随机选择一个点作为新质心
                new_centroids.append(random.choice(points))
        if centroids == new_centroids: break
        centroids = new_centroids
    return centroids

线性模型

模型	公式	损失函数
线性回归	$\hat{y}=w^Tx+b$	均方误差：$\frac{1}{n}\sum(y-\hat{y})^2$
逻辑回归	$\hat{y}=\sigma(w^Tx+b)$	交叉熵
岭回归	线性 + $L_2$ 惩罚项	$L=\text{MSE}+\lambda|w|^2$
Lasso 回归	线性 + $L_1$ 惩罚项	$L=\text{MSE}+\lambda|w|_1$

微型代码（线性回归的梯度下降）：

def train(X, y, lr=0.01, epochs=1000):
    w = [0]*len(X[0])
    b = 0
    for _ in range(epochs):
        for i in range(len(y)):
            # 计算预测值
            y_pred = sum(w[j]*X[i][j] for j in range(len(w))) + b
            err = y_pred - y[i]
            # 更新权重和偏置
            for j in range(len(w)):
                w[j] -= lr * err * X[i][j]
            b -= lr * err
    return w, b

决策树与集成方法

算法	描述	备注
ID3 / C4.5 / CART	基于信息增益或基尼指数进行分割	递归的，可解释性强
随机森林	Bagging + 决策树	降低方差
梯度提升	顺序拟合残差	XGBoost, LightGBM, CatBoost
AdaBoost	加权弱学习器	对噪声敏感

不纯度度量：

• 基尼指数：$1-\sum p_i^2$
• 熵：$-\sum p_i\log_2p_i$

支持向量机 (SVM)

寻找最大间隔超平面。

目标函数： $$ \min_{w,b} \frac{1}{2}|w|^2 + C\sum\xi_i $$ 约束条件：$y_i(w^Tx_i+b)\ge1-\xi_i$

核技巧实现非线性分离： $$K(x_i,x_j)=\phi(x_i)\cdot\phi(x_j)$$

神经网络基础

组件	描述
神经元	$y=\sigma(w\cdot x+b)$
激活函数	Sigmoid, ReLU, Tanh
损失函数	均方误差，交叉熵
训练	梯度下降 + 反向传播
优化器	SGD, Adam, RMSProp

前向传播： $$a^{(l)} = \sigma(W^{(l)}a^{(l-1)}+b^{(l)})$$ 反向传播逐层计算梯度。

梯度下降变体

变体	思想	备注
批量	每一步使用所有数据	稳定但慢
随机	每个样本更新一次	有噪声，快
小批量	分组更新	常见做法
动量	添加速度项	收敛更快
Adam	自适应矩估计	最流行

更新规则： $$ w = w - \eta \cdot \frac{\partial L}{\partial w} $$

无监督学习

算法	描述	备注
PCA	基于方差的投影	特征分解
ICA	独立成分分析	信号分离
t-SNE	保持局部结构	仅用于可视化
自编码器	神经网络重构模型	降维

PCA 公式： 协方差矩阵 $C=\frac{1}{n}X^TX$，$C$ 的特征向量是主成分轴。

概率模型

模型	描述	备注
朴素贝叶斯	独立性假设	$P(y	x)\propto P(y)\prod P(x_i	y)$
隐马尔可夫模型	序列隐状态	Viterbi 算法解码
马尔可夫链	转移概率	$P(x_t	x_{t-1})$
高斯混合模型	软聚类	EM 算法

优化与元启发式算法

算法	类别	备注
梯度下降	凸优化	目标函数可微
牛顿法	二阶方法	使用海森矩阵
模拟退火	概率搜索	逃离局部最小值
遗传算法	进化算法	基于种群的搜索
粒子群优化	集体移动	受群体行为启发
爬山算法	贪心搜索	局部优化

强化学习核心

概念	描述	示例
智能体	学习者/决策者	机器人，策略
环境	提供状态和奖励	游戏，模拟器
策略	状态到动作的映射	$\pi(s)=a$
价值函数	期望回报	$V(s)$, $Q(s,a)$

Q-Learning 更新： $$ Q(s,a)\leftarrow Q(s,a)+\alpha(r+\gamma\max_{a'}Q(s',a')-Q(s,a)) $$

微型代码：

Q[s][a] += alpha * (r + gamma * max(Q[s_next]) - Q[s][a])

AI 搜索算法

算法	描述	复杂度	备注
BFS	无权图最短路径	$O(V+E)$	层序搜索
DFS	深度探索	$O(V+E)$	回溯
A* 搜索	启发式搜索	$O(E\log V)$	$f(n)=g(n)+h(n)$
IDA*	迭代加深 A*	内存效率高	若 $h$ 可采纳则最优
束搜索	保留最好的 k 个状态	近似	NLP 解码

评估指标

任务	指标	公式 / 含义
分类	准确率，精确率，召回率	$\frac{TP}{TP+FP}$, $\frac{TP}{TP+FN}$
回归	RMSE, MAE, $R^2$	拟合度与误差大小
聚类	轮廓系数	内聚性与分离性
排序	MAP, NDCG	顺序敏感

混淆矩阵：

	预测 +	预测 -
实际 +	TP	FN
实际 -	FP	TN

总结

类别	算法示例	备注
聚类	k-Means, GMM	无监督分组
分类	逻辑回归，SVM，决策树	有监督标注
回归	线性回归，岭回归，Lasso	预测连续值
优化	GD, Adam, 模拟退火	最小化损失
概率	贝叶斯，HMM，EM	不确定性建模
强化学习	Q-Learning, SARSA	基于奖励的学习