不追求学术严谨,用大白话讲清楚 AI 需要的算法
很多人学 AI 的时候,上来就学 PyTorch、调模型、跑训练。结果一遇到模型不收敛、推理太慢、内存爆了,就懵了。根本原因往往是:算法基础没打好。
学 AI 不懂算法,就像学开车不懂交通规则。你可以踩油门往前走,但遇到交叉路口就不知道该怎么走了,出了事故也不知道为什么。算法就是 AI 的"交通规则"——它决定了你是在用 AI,还是在理解 AI。
打开任何一个深度学习框架的代码,你会发现到处都是算法:
| 场景 | 不懂算法 | 懂算法 |
|---|---|---|
| 推理太慢 | 只会加 GPU | 用 FlashAttention、KV Cache 优化 |
| 向量检索慢 | 暴力搜索 | 用 HNSW/IVF 加速 1000 倍 |
| 模型太大 | 换小模型 | 用剪枝/量化/蒸馏压缩 |
| 训练不收敛 | 无脑调参 | 从优化算法原理分析问题 |
| RLHF 对齐 | 照着教程抄 | 理解 PPO/DPO 算法本质 |
| 超参搜索 | 网格搜索 | 用贝叶斯优化/MCTS 高效搜索 |
AI 工程师需要的算法,和 ACM 竞赛侧重点不同。你不需要手写红黑树,不需要背诵 200 种 DP 状态转移方程。你需要的是:直觉(这个算法在做什么)+ 应用(它在 AI 里怎么用)+ 动手(用 Python 能跑通)。这本教程就是按这个思路写的。
在选择算法时,我们不仅关心它"能不能解决问题",更关心它"解决问题有多快、多省资源"。这就是复杂度分析——评估算法效率的数学工具。
假设你要从一本 1000 页的字典里找一个词。方法一:从第一页翻到最后一页(线性搜索)。方法二:先翻到中间,判断目标在前半还是后半,再对那一半重复(二分查找)。方法一平均要翻 500 次,方法二最多翻 10 次。复杂度分析就是比较这两种方法的"翻页次数"。
大 O 表示法描述的是:当输入规模 n 趋向无穷大时,算法的运行时间增长有多快。它忽略常数系数和低阶项,只关注"增长的量级"。
AI 的数据规模通常是百万甚至十亿级别。O(n²) 的算法在 n=1000 时还能跑,n=1000000 时就完全不可用了。比如朴素的注意力机制是 O(n²),这就是为什么 FlashAttention(O(n))是重大突破。
| 时间复杂度 | 空间复杂度 | |
|---|---|---|
| 衡量什么 | 算法执行了多少步操作 | 算法需要多少额外内存 |
| 关注点 | 快不快 | 省内存不省内存 |
| 典型权衡 | 用空间换时间(哈希表) | 用时间换空间(原地排序) |
时间复杂度 = 搬完所有东西需要多久。空间复杂度 = 需要多大的货车。你可以一趟慢慢搬(省空间、费时间),也可以叫 10 辆车同时搬(费空间、省时间)。算法设计就是在两者之间找平衡。
有些操作偶尔很贵,但大部分时候很便宜。摊销分析把所有操作的总成本平均分摊。
停车场每小时 10 元,但早上第一次停车收 50 元。每天停 8 小时,总费用 120 元。均摊每小时 15 元。
Python 的 list.append() 在底层数组满了时需要扩容(复制所有元素),单次是 O(n)。但因为扩容是指数级增长的,n 次 append 总成本 O(n),均摊每次 O(1)。放心用它收集 loss 值。
"O(n) 一定比 O(n²) 快"——错!大 O 描述增长趋势,不是绝对速度。当 n 很小时,O(n²) 可能更快。但 AI 场景的 n 通常很大,大 O 分析非常有意义。
数组和链表是最基础的两种数据结构,所有其他数据结构都在它们之上构建。
数组就像一排连续编号的储物柜——你可以直接走到 7 号柜拿东西(O(1)),但要在中间插入一个新柜子,就得把后面的全挪一遍(O(n))。
链表就像寻宝游戏——每个线索告诉你下一个线索在哪里。你必须从头顺着找(O(n)),但插入新线索只需要改两个指针(O(1))。
数组在内存中是一块连续的空间。因为连续,所以:
PyTorch 的 Tensor、NumPy 的 ndarray,底层都是连续内存块。一张 224×224×3 的图片就是一个 150528 个数字的连续数组。NumPy 比 Python list 快 100 倍——NumPy 直接操作连续内存,Python list 每个元素都要做类型检查和指针解引用。
链表的每个节点包含数据和指向下一个节点的指针。
| 操作 | 数组 | 链表 |
|---|---|---|
| 随机访问 | O(1) ✅ | O(n) ❌ |
| 头部插入 | O(n) ❌ | O(1) ✅ |
| 尾部插入 | 均摊 O(1) ✅ | O(1)(有尾指针)✅ |
| 内存开销 | 小(只存数据) | 大(数据 + 指针) |
| 缓存友好 | 非常好 ✅ | 差 ❌ |
绝大多数 AI 场景用数组(Tensor)。链表在 AI 中较少直接使用,但理解它对理解哈希表(链地址法)、图的邻接表、LRU 缓存等至关重要。
在循环中反复 list.insert(0, x) 是 O(n²) 的——每次都在头部插入。用 collections.deque(双端队列),它是 O(1) 的。
class ListNode:
"""链表节点"""
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class LinkedList:
"""单链表:插入、删除、反转、遍历"""
def __init__(self):
self.head = None
def insert_head(self, val):
"""头部插入 O(1)"""
node = ListNode(val, self.head)
self.head = node
def insert_tail(self, val):
"""尾部插入 O(n)"""
node = ListNode(val)
if not self.head:
self.head = node
return
cur = self.head
while cur.next:
cur = cur.next
cur.next = node
def delete(self, val):
"""删除第一个值为 val 的节点 O(n)"""
dummy = ListNode(0, self.head)
prev, cur = dummy, self.head
while cur:
if cur.val == val:
prev.next = cur.next
break
prev, cur = cur, cur.next
self.head = dummy.next
def reverse(self):
"""反转链表 O(n)"""
prev, cur = None, self.head
while cur:
nxt = cur.next
cur.next = prev
prev = cur
cur = nxt
self.head = prev
def to_list(self):
"""转为 Python 列表"""
result, cur = [], self.head
while cur:
result.append(cur.val)
cur = cur.next
return result
# 测试
ll = LinkedList()
for x in [1, 2, 3, 4, 5]:
ll.insert_tail(x)
print(f"原始: {ll.to_list()}") # [1, 2, 3, 4, 5]
ll.delete(3)
print(f"删除 3: {ll.to_list()}") # [1, 2, 4, 5]
ll.reverse()
print(f"反转: {ll.to_list()}") # [5, 4, 2, 1]
栈和队列是两种"限制了操作方式"的线性表——你不能随便访问中间的元素,只能在特定位置操作。
栈就像一摞盘子——你只能从最上面拿(后进先出 LIFO)。
队列就像排队买奶茶——先排队的人先买到(先进先出 FIFO)。
栈只支持两个核心操作:
允许两端进行插入和删除。Python 的 collections.deque 底层是分段数组,两端操作都是 O(1)。
单调栈——栈内元素保持单调递增或递减。用于"下一个更大元素"、"柱状图最大矩形"。
单调队列——队列内元素保持单调。用于"滑动窗口最大值"。
# 1. 用栈实现括号匹配
def is_valid_parentheses(s):
stack = []
mapping = {')': '(', ']': '[', '}': '{'}
for c in s:
if c in mapping:
if not stack or stack[-1] != mapping[c]:
return False
stack.pop()
else:
stack.append(c)
return not stack
print(is_valid_parentheses("({[]})")) # True
print(is_valid_parentheses("([)]")) # False
# 2. 单调栈:找每个元素右边第一个比它大的数
def next_greater_element(nums):
n = len(nums)
result = [-1] * n
stack = [] # 存下标,对应值单调递减
for i in range(n):
while stack and nums[i] > nums[stack[-1]]:
result[stack.pop()] = nums[i]
stack.append(i)
return result
print(next_greater_element([2, 1, 2, 4, 3])) # [4, 2, 4, -1, -1]
# 3. 用队列实现 BFS
from collections import deque
def bfs_level_order(root):
"""二叉树层序遍历"""
if not root: return []
result, queue = [], deque([root])
while queue:
level = []
for _ in range(len(queue)):
node = queue.popleft()
level.append(node.val)
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
result.append(level)
return result
哈希表能在 O(1) 时间内完成查找、插入和删除。Python 的 dict 和 set 底层就是哈希表。
想象一个有 1000 个抽屉的柜子。你把书名的字母加起来,除以 1000 取余数,得到抽屉编号。下次找书再算一次公式,直接去那个抽屉拿——不需要翻遍整个柜子。
好的哈希函数有三个特点:
{"hello": 15, "world": 23}布隆过滤器是一种空间效率极高的概率型数据结构,用于判断元素是否可能在集合中。
当数据量极大(十亿级),普通哈希表太耗内存。布隆过滤器用极小空间就能快速判断"这个 URL 有没有爬过"。在 RAG 中可以用它快速过滤明显不相关的文档。
import hashlib
import numpy as np
class BloomFilter:
"""布隆过滤器:概率型数据结构,判断元素是否可能存在"""
def __init__(self, expected_items=10000, fp_rate=0.01):
# 根据期望元素数和误判率计算最优参数
self.size = int(-expected_items * np.log(fp_rate) / (np.log(2) ** 2))
self.n_hashes = int(self.size / expected_items * np.log(2))
self.bit_array = np.zeros(self.size, dtype=bool)
self.count = 0
def _hashes(self, item):
"""生成 k 个哈希值"""
item_bytes = str(item).encode('utf-8')
h1 = int(hashlib.md5(item_bytes).hexdigest(), 16)
h2 = int(hashlib.sha256(item_bytes).hexdigest(), 16)
for i in range(self.n_hashes):
yield (h1 + i * h2) % self.size
def add(self, item):
"""插入元素"""
for idx in self._hashes(item):
self.bit_array[idx] = True
self.count += 1
def might_contain(self, item):
"""判断元素是否可能存在(False = 一定不存在,True = 可能存在)"""
return all(self.bit_array[idx] for idx in self._hashes(item))
# 示例
bf = BloomFilter(expected_items=10000, fp_rate=0.01)
print(f"位数组大小: {bf.size} bits ({bf.size/8/1024:.1f} KB)")
print(f"哈希函数数量: {bf.n_hashes}")
# 插入
for i in range(10000):
bf.add(f"item_{i}")
# 查询
print(f"'item_0' 可能存在: {bf.might_contain('item_0')}") # True
print(f"'item_9999' 可能存在: {bf.might_contain('item_9999')}") # True
print(f"'not_exist' 可能存在: {bf.might_contain('not_exist')}") # 大概率 False
# 统计误判率
false_positives = sum(1 for i in range(10000, 20000) if bf.might_contain(f"item_{i}"))
print(f"实际误判率: {false_positives/10000:.2%}") # ≈ 1%
# 1. 两数之和(哈希表经典应用)
def two_sum(nums, target):
seen = {}
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
return []
print(two_sum([2, 7, 11, 15], 9)) # [0, 1]
# 2. 字符串哈希(Rabin-Karp 用到)
def string_hash(s, base=31, mod=10**9+7):
"""多项式哈希:把字符串映射为一个整数"""
h = 0
for c in s:
h = (h * base + ord(c)) % mod
return h
print(string_hash("hello")) # 一个大整数
# 3. LRU 缓存(哈希表 + 双向链表)
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
self.cache = OrderedDict()
self.capacity = capacity
def get(self, key):
if key not in self.cache: return -1
self.cache.move_to_end(key)
return self.cache[key]
def put(self, key, value):
if key in self.cache:
self.cache.move_to_end(key)
self.cache[key] = value
if len(self.cache) > self.capacity:
self.cache.popitem(last=False)
树是一种分层的数据结构——从根节点开始,每个节点可以有多个子节点。文件系统、HTML DOM、家谱都是树形结构。
家谱树:最上面是老祖宗(根节点),老祖宗有几个孩子,每个孩子又有自己的孩子。每个人只有一个父亲(除了根),但可以有多个孩子。这就是树——层次化 + 无环。
二叉树的每个节点最多有两个子节点:左孩子和右孩子。三种遍历:
自动微分就是后序遍历——先计算所有子节点的梯度,再计算当前节点的梯度。PyTorch 的 loss.backward() 就是这样工作的。
BST:左子树所有节点 < 根 < 右子树所有节点。查找、插入、删除都是 O(log n)(平衡时)。
按顺序插入 1,2,3,4,5,BST 退化成链表,O(n)。解决方案:平衡树(AVL、红黑树)通过旋转保持平衡。
KD-Tree 对 k 维空间进行划分,用于快速找最近邻。在低维(<20 维)效果好,高维时退化。向量数据库用 HNSW 而不是 KD-Tree。
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# 1. 三种遍历
def inorder(root):
"""中序遍历(左→根→右):BST 中得到有序序列"""
return inorder(root.left) + [root.val] + inorder(root.right) if root else []
def preorder(root):
"""前序遍历(根→左→右):用于序列化树"""
return [root.val] + preorder(root.left) + preorder(root.right) if root else []
def postorder(root):
"""后序遍历(左→右→根):自动微分的计算顺序"""
return postorder(root.left) + postorder(root.right) + [root.val] if root else []
# 2. 递归求最大深度
def max_depth(root):
if not root: return 0
return max(max_depth(root.left), max_depth(root.right)) + 1
# 3. BST 查找
def bst_search(root, target):
if not root: return False
if target == root.val: return True
elif target < root.val: return bst_search(root.left, target)
else: return bst_search(root.right, target)
# 4. BST 插入
def bst_insert(root, val):
if not root: return TreeNode(val)
if val < root.val: root.left = bst_insert(root.left, val)
else: root.right = bst_insert(root.right, val)
return root
LCA(Lowest Common Ancestor)是树上最常用的操作之一:给定两个节点,找到它们最近的公共祖先。在文件系统中就是"最近的共同父目录"。
# 5. 最近公共祖先(LCA)
def lowest_common_ancestor(root, p, q):
"""
二叉树 LCA:递归解法
如果 p 和 q 分别在当前节点的左右子树中,当前节点就是 LCA
时间 O(n),空间 O(h)(h = 树高)
"""
if not root or root.val == p or root.val == q:
return root
left = lowest_common_ancestor(root.left, p, q)
right = lowest_common_ancestor(root.right, p, q)
if left and right: return root # p 和 q 分布在两侧
return left if left else right # 都在一侧
# 构建示例树: 3
# / \
# 5 1
# / \ / \
# 6 2 0 8
# / \
# 7 4
root = TreeNode(3)
root.left = TreeNode(5); root.right = TreeNode(1)
root.left.left = TreeNode(6); root.left.right = TreeNode(2)
root.right.left = TreeNode(0); root.right.right = TreeNode(8)
root.left.right.left = TreeNode(7); root.left.right.right = TreeNode(4)
lca = lowest_common_ancestor(root, 5, 1)
print(f"LCA(5, 1) = {lca.val}") # 3
lca = lowest_common_ancestor(root, 5, 4)
print(f"LCA(5, 4) = {lca.val}") # 5
# 6. BST 的 LCA(利用有序性质,更高效)
def lca_bst(root, p, q):
"""BST 的 LCA:利用左 < 根 < 右的性质"""
while root:
if p < root.val and q < root.val:
root = root.left
elif p > root.val and q > root.val:
root = root.right
else:
return root
return None
堆能高效地找到最大值或最小值。优先队列是基于堆的抽象数据类型——每次取出优先级最高的元素。
医院急诊室——不是先来后到,而是按病情严重程度排序。病情最重的先看。堆就是实现这种"动态取最值"的数据结构。
堆用数组实现:对于下标 i,左孩子 = 2i+1,右孩子 = 2i+2,父节点 = (i-1)/2。
import heapq
data = [3, 1, 4, 1, 5, 9]
heapq.heapify(data) # 最小堆: [1, 1, 4, 3, 5, 9]
heapq.heappush(data, 2) # 插入 2
smallest = heapq.heappop(data) # 弹出 1class MinHeap:
"""最小堆:手写实现"""
def __init__(self):
self.data = []
def push(self, val):
self.data.append(val)
self._sift_up(len(self.data) - 1)
def pop(self):
if not self.data: return None
top = self.data[0]
last = self.data.pop()
if self.data:
self.data[0] = last
self._sift_down(0)
return top
def peek(self):
return self.data[0] if self.data else None
def _sift_up(self, i):
while i > 0:
parent = (i - 1) // 2
if self.data[i] < self.data[parent]:
self.data[i], self.data[parent] = self.data[parent], self.data[i]
i = parent
else: break
def _sift_down(self, i):
n = len(self.data)
while True:
smallest = i
left, right = 2*i+1, 2*i+2
if left < n and self.data[left] < self.data[smallest]:
smallest = left
if right < n and self.data[right] < self.data[smallest]:
smallest = right
if smallest != i:
self.data[i], self.data[smallest] = self.data[smallest], self.data[i]
i = smallest
else: break
# 测试
heap = MinHeap()
for x in [3, 1, 4, 1, 5, 9]:
heap.push(x)
print([heap.pop() for _ in range(6)]) # [1, 1, 3, 4, 5, 9]
图是最通用的数据结构——能表达任意实体之间的关系。社交网络、知识图谱、神经网络都是图。
城市公路网:城市是节点,公路是边。公路有长度就是加权图,单行道就是有向图。
| 邻接矩阵 | 邻接表 | |
|---|---|---|
| 空间 | O(V²) | O(V + E) |
| 查边 | O(1) | O(度数) |
| 适用 | 稠密图 | 稀疏图 |
对 DAG 进行排序,使得每条边 (u,v) 中 u 排在 v 前面。
计算图是 DAG,拓扑排序决定反向传播的计算顺序——必须先算依赖节点的梯度。这就是 loss.backward() 能正确工作的原因。
连通分量:互相可达的最大节点集合。用 DFS/BFS 找。环检测:有向图用 DFS 三色标记法,无向图用并查集。
from collections import deque, defaultdict
# 1. 图的邻接表表示
class Graph:
def __init__(self, directed=False):
self.graph = defaultdict(list)
self.directed = directed
def add_edge(self, u, v, w=1):
self.graph[u].append((v, w))
if not self.directed:
self.graph[v].append((u, w))
def bfs(self, start):
"""BFS:返回访问顺序"""
visited = {start}
queue = deque([start])
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor, _ in self.graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return order
def dfs(self, start, visited=None):
"""DFS:返回访问顺序"""
if visited is None: visited = set()
visited.add(start)
order = [start]
for neighbor, _ in self.graph[start]:
if neighbor not in visited:
order.extend(self.dfs(neighbor, visited))
return order
def has_cycle(self):
"""有向图环检测:三色标记法"""
WHITE, GRAY, BLACK = 0, 1, 2
color = defaultdict(int)
def dfs(node):
color[node] = GRAY
for neighbor, _ in self.graph[node]:
if color[neighbor] == GRAY: return True
if color[neighbor] == WHITE and dfs(neighbor): return True
color[node] = BLACK
return False
return any(dfs(node) for node in self.graph if color[node] == WHITE)
# 2. 拓扑排序
def topological_sort(graph, n):
"""Kahn 算法:BFS 拓扑排序"""
in_degree = [0] * n
for u in graph:
for v, _ in graph[u]:
in_degree[v] += 1
queue = deque(i for i in range(n) if in_degree[i] == 0)
order = []
while queue:
node = queue.popleft()
order.append(node)
for v, _ in graph[node]:
in_degree[v] -= 1
if in_degree[v] == 0: queue.append(v)
return order if len(order) == n else [] # 有环则返回空
最短路径是图论中最经典的问题:从 A 到 B,怎么走最近?在 AI 中,最短路径算法的思想被广泛应用于注意力机制、路径规划和资源分配。
你用导航从家到公司。导航不只是看距离,还会考虑路况(权重)。它在背后运行的就是最短路径算法——找到"距离 × 时间"最小的路线。
Dijkstra 解决的是单源最短路径问题:从一个起点出发,到所有其他点的最短距离。
Dijkstra 不能处理负权边。如果有负权边,用 Bellman-Ford 算法。
能处理负权边的最短路径算法。对所有边松弛 V-1 次。复杂度 O(VE)。
强化学习的核心公式——Bellman 方程——本质上就是最短路径的推广。Q-Learning 的更新规则和 Bellman-Ford 的松弛操作如出一辙:Q(s,a) = r + γ·max Q(s',a'),就是"通过这个状态能不能让回报更高"。
求所有点对之间的最短路径。O(V³)。核心思想:对于每对 (i,j),检查"经过中间点 k 会不会更短"。
网络流问题:在有容量限制的图中,从源点到汇点最多能输送多少"流量"。Ford-Fulkerson 方法通过反复找增广路径来增加流量。
Transformer 的注意力机制可以类比为网络流——每个 token 是一个节点,注意力权重是边的"容量"。信息从输入流向输出,注意力权重决定了信息的分配。
import heapq
from collections import defaultdict
def dijkstra(graph, start):
"""
Dijkstra 最短路径
graph: {node: [(neighbor, weight), ...]}
返回: {node: 最短距离}
"""
dist = {start: 0}
heap = [(0, start)]
prev = {start: None}
while heap:
d, u = heapq.heappop(heap)
if d > dist.get(u, float('inf')):
continue
for v, w in graph[u]:
new_dist = d + w
if new_dist < dist.get(v, float('inf')):
dist[v] = new_dist
prev[v] = u
heapq.heappush(heap, (new_dist, v))
return dist, prev
def get_path(prev, target):
"""回溯最短路径"""
path = []
while target is not None:
path.append(target)
target = prev[target]
return path[::-1]
# 示例
graph = {
'A': [('B', 1), ('C', 4)],
'B': [('A', 1), ('C', 2), ('D', 5)],
'C': [('A', 4), ('B', 2), ('D', 1)],
'D': [('B', 5), ('C', 1)]
}
dist, prev = dijkstra(graph, 'A')
print(f"最短距离: {dist}") # {'A':0, 'B':1, 'C':3, 'D':4}
print(f"A→D 路径: {get_path(prev, 'D')}") # ['A', 'B', 'C', 'D']
def floyd_warshall(n, edges):
"""所有点对最短路径。n 个节点,edges = [(u,v,w), ...]"""
INF = float('inf')
dist = [[INF] * n for _ in range(n)]
for i in range(n): dist[i][i] = 0
for u, v, w in edges:
dist[u][v] = w
for k in range(n):
for i in range(n):
for j in range(n):
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
return dist
# 示例
edges = [(0,1,3), (0,2,8), (1,2,2), (2,3,1)]
result = floyd_warshall(4, edges)
print("最短距离矩阵:")
for row in result:
print([x if x < float('inf') else '∞' for x in row])
并查集(Union-Find)是一种处理"分组"问题的数据结构——高效地判断两个元素是否在同一组,以及合并两个组。
想象一个社交网络。一开始每个人都是一"族"。每当两个人成为朋友,就把他们所在的族合并。并查集就是高效管理这些"族"的数据结构——回答"我和他是不是一族?"只需 O(1)。
经过两种优化后,每次操作的均摊复杂度是 O(α(n)),其中 α 是反阿克曼函数,对于实际数据几乎是 O(1)。
class UnionFind:
"""并查集:路径压缩 + 按秩合并"""
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
self.count = n # 连通分量数
def find(self, x):
"""查找根节点(路径压缩)"""
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
"""合并两个集合(按秩合并)"""
px, py = self.find(x), self.find(y)
if px == py: return False
if self.rank[px] < self.rank[py]: px, py = py, px
self.parent[py] = px
if self.rank[px] == self.rank[py]: self.rank[px] += 1
self.count -= 1
return True
def connected(self, x, y):
return self.find(x) == self.find(y)
# 示例:社交网络连通性
uf = UnionFind(6)
uf.union(0, 1); uf.union(1, 2); uf.union(3, 4)
print(f"连通分量数: {uf.count}") # 3
print(f"0 和 2 连通: {uf.connected(0, 2)}") # True
print(f"0 和 3 连通: {uf.connected(0, 3)}") # False
import numpy as np
def kmeans(X, k, max_iters=100):
"""K-Means 聚类"""
n, d = X.shape
# 随机选 k 个初始中心
centroids = X[np.random.choice(n, k, replace=False)]
labels = np.zeros(n, dtype=int)
for iteration in range(max_iters):
# 分配:每个点找最近的中心
for i in range(n):
dists = np.linalg.norm(X[i] - centroids, axis=1)
labels[i] = np.argmin(dists)
# 更新:重新计算中心
new_centroids = np.array([X[labels == j].mean(axis=0) for j in range(k)])
# 收敛判断
if np.allclose(centroids, new_centroids):
print(f"在第 {iteration} 轮收敛")
break
centroids = new_centroids
return labels, centroids
# 示例
np.random.seed(42)
X = np.vstack([np.random.randn(50, 2) + [2, 2],
np.random.randn(50, 2) + [-2, -2],
np.random.randn(50, 2) + [2, -2]])
labels, centers = kmeans(X, k=3)
print(f"聚类中心:\n{np.round(centers, 2)}")
随机初始化可能导致聚类效果很差。K-Means++ 的策略:第一个中心随机选,后续中心按"离已有中心越远,概率越大"来选择。这样初始中心天然分散,收敛更快、效果更好。
如果两个初始中心靠得很近,它们大概率属于同一个簇,等于浪费了一个中心。K-Means++ 通过概率加权避免了这个问题——它是 O(log k) 近似最优的。
def kmeans_plusplus_init(X, k):
"""K-Means++ 初始化:按概率选择离已有中心最远的点"""
n, d = X.shape
centroids = []
# 1. 随机选第一个中心
centroids.append(X[np.random.randint(n)])
for _ in range(1, k):
# 2. 计算每个点到最近中心的距离的平方
dists = np.array([min(np.linalg.norm(x - c) ** 2 for c in centroids) for x in X])
# 3. 按距离平方的概率选择下一个中心
probs = dists / dists.sum()
next_idx = np.random.choice(n, p=probs)
centroids.append(X[next_idx])
return np.array(centroids)
def kmeans_pp(X, k, max_iters=100):
"""K-Means + K-Means++ 初始化"""
n, d = X.shape
centroids = kmeans_plusplus_init(X, k)
labels = np.zeros(n, dtype=int)
for iteration in range(max_iters):
# 分配
for i in range(n):
dists = np.linalg.norm(X[i] - centroids, axis=1)
labels[i] = np.argmin(dists)
# 更新
new_centroids = np.array([X[labels == j].mean(axis=0) for j in range(k)])
if np.allclose(centroids, new_centroids):
break
centroids = new_centroids
return labels, centroids
# 对比:随机初始化 vs K-Means++
np.random.seed(42)
X = np.vstack([np.random.randn(50, 2) + [5, 5],
np.random.randn(50, 2) + [-5, -5],
np.random.randn(50, 2) + [5, -5]])
# 随机初始化(可能很差)
labels_rand, _ = kmeans(X, k=3)
# K-Means++ 初始化(更稳定)
labels_pp, _ = kmeans_pp(X, k=3)
from collections import Counter
print(f"随机初始化簇大小: {Counter(labels_rand)}")
print(f"K-Means++ 簇大小: {Counter(labels_pp)}")
DBSCAN(Density-Based Spatial Clustering of Applications with Noise)的核心思想:密度可达的点属于同一簇,低密度区域的点是噪声。不需要指定 K,能发现任意形状的簇。
def dbscan(X, eps=0.5, min_samples=5):
"""
DBSCAN 密度聚类
X: 数据点 [n, d]
eps: ε 邻域半径
min_samples: 成为核心点的最小邻居数
"""
n = X.shape[0]
labels = np.full(n, -1) # -1 表示噪声
cluster_id = 0
# 预计算距离矩阵
dists = np.linalg.norm(X[:, None] - X[None, :], axis=-1)
visited = np.zeros(n, dtype=bool)
for i in range(n):
if visited[i]:
continue
visited[i] = True
# 找 ε 邻域内的邻居
neighbors = np.where(dists[i] <= eps)[0]
if len(neighbors) < min_samples:
# 标记为噪声(后面可能被重新归类为边界点)
labels[i] = -1
else:
# 开始一个新簇
labels[i] = cluster_id
# 用队列扩展簇
seed_set = list(neighbors)
j = 0
while j < len(seed_set):
q = seed_set[j]
if not visited[q]:
visited[q] = True
q_neighbors = np.where(dists[q] <= eps)[0]
if len(q_neighbors) >= min_samples:
seed_set.extend(q_neighbors) # 核心点的邻居也加入
if labels[q] == -1:
labels[q] = cluster_id # 噪声点变为边界点
elif labels[q] == -1 or labels[q] == -1:
labels[q] = cluster_id
j += 1
cluster_id += 1
return labels
# 示例:月牙形数据(K-Means 搞不定,DBSCAN 轻松解决)
np.random.seed(42)
from math import pi
t1 = np.random.uniform(0, pi, 80)
moon1 = np.column_stack([np.cos(t1), np.sin(t1)]) + np.random.randn(80, 2) * 0.1
t2 = np.random.uniform(0, pi, 80)
moon2 = np.column_stack([1 - np.cos(t2), 1 - np.sin(t2) - 0.5]) + np.random.randn(80, 2) * 0.1
X_moons = np.vstack([moon1, moon2])
labels_db = dbscan(X_moons, eps=0.4, min_samples=5)
n_clusters = len(set(labels_db)) - (1 if -1 in labels_db else 0)
n_noise = list(labels_db).count(-1)
print(f"DBSCAN 发现 {n_clusters} 个簇,{n_noise} 个噪声点")
K-Means 需要指定 K,但怎么选?肘部法则:计算不同 K 值的簇内平方和(SSE),画出曲线,找"肘部"——SSE 下降速度突然变缓的点。
def elbow_method(X, k_range=range(1, 11)):
"""肘部法则:找最优 K 值"""
sse_list = []
for k in k_range:
labels, centroids = kmeans_pp(X, k)
sse = sum(np.linalg.norm(X[labels == j] - centroids[j]) ** 2 for j in range(k))
sse_list.append(sse)
print(f"K={k}: SSE={sse:.1f}")
# 自动检测肘部(最大曲率点)
# 用二阶差分找拐点
if len(sse_list) >= 3:
diffs = np.diff(sse_list)
ddiffs = np.diff(diffs)
elbow_k = np.argmax(ddiffs) + 2 # +2 因为两次 diff 偏移
print(f"\n肘部法则建议 K = {elbow_k}")
return sse_list
np.random.seed(42)
X = np.vstack([np.random.randn(50, 2) + [3, 3],
np.random.randn(50, 2) + [-3, -3],
np.random.randn(50, 2) + [3, -3]])
elbow_method(X)
当你有十亿个向量,要找到和查询向量最相似的那个,暴力搜索太慢。近似最近邻(ANN)算法用少量精度换取巨大的速度提升——这就是向量数据库的核心。
你在一个有 100 万本书的图书馆里找和某本书"内容最相似"的书。逐本比较要 100 万次。但如果你先把书按主题分类放到不同书架(聚类),然后只在最相关的几个书架里找,可能只需要比较 1000 本——快了 1000 倍,而且几乎不会错过最好的那本。
LSH 的核心思想:设计一种哈希函数,让相似的向量大概率映射到同一个桶。
HNSW 是目前最流行的 ANN 算法,几乎所有向量数据库都支持它。
RAG(检索增强生成)的核心是向量检索:把文档切成 chunks,用 Embedding 模型转成向量,存入向量数据库(Milvus、Pinecone、Qdrant)。用户提问时,先用 HNSW 找到最相关的几个 chunk,再喂给 LLM 生成回答。HNSW 的搜索速度决定了 RAG 的响应时间。
先把所有向量用 K-Means 聚成若干个簇。查询时,先找到最近的几个簇中心,再在这些簇内搜索。
把高维向量切成若干子向量,每个子向量用 K-Means 聚类,用聚类中心的编号代替原始向量。压缩比极高,搜索时用查表法快速计算距离。
实际的向量数据库通常组合使用:IVF + PQ + HNSW。先用 IVF 粗筛,再用 PQ 压缩,最后用 HNSW 精搜。Faiss 库就是这种组合架构。
import numpy as np
# 1. 暴力最近邻(精确,作为基准)
def brute_force_nn(database, query, k=5):
"""暴力搜索:O(nd) 计算所有距离"""
dists = np.linalg.norm(database - query, axis=1)
top_k = np.argsort(dists)[:k]
return top_k, dists[top_k]
# 2. 余弦相似度搜索
def cosine_search(database, query, k=5):
"""余弦相似度:用于文本 Embedding 检索"""
# 归一化
db_norm = database / np.linalg.norm(database, axis=1, keepdims=True)
q_norm = query / np.linalg.norm(query)
# 点积 = 余弦相似度
similarities = db_norm @ q_norm
top_k = np.argsort(similarities)[::-1][:k]
return top_k, similarities[top_k]
# 3. LSH 实现
class LSH:
"""局部敏感哈希:用随机超平面做哈希"""
def __init__(self, dim, n_tables=10, n_bits=16):
self.tables = n_tables
self.bits = n_bits
# 随机超平面
self.planes = [np.random.randn(n_bits, dim) for _ in range(n_tables)]
self.hash_tables = [defaultdict(list) for _ in range(n_tables)]
def _hash(self, vec, table_idx):
projections = self.planes[table_idx] @ vec
return tuple((projections > 0).astype(int))
def insert(self, vec, idx):
for t in range(self.tables):
h = self._hash(vec, t)
self.hash_tables[t][h].append(idx)
def query(self, vec, max_candidates=100):
candidates = set()
for t in range(self.tables):
h = self._hash(vec, t)
candidates.update(self.hash_tables[t][h])
if len(candidates) >= max_candidates:
break
return list(candidates)[:max_candidates]
# 示例
np.random.seed(42)
database = np.random.randn(10000, 128)
query = np.random.randn(128)
idxs, dists = brute_force_nn(database, query, k=5)
print(f"最近邻索引: {idxs}")
手写 LSH 仅用于理解原理。工业界用 Faiss(Facebook AI Similarity Search),支持百万级向量高效检索。
import faiss
import numpy as np
import time
np.random.seed(42)
dim = 128
nb = 1000000 # 百万级向量库
nq = 1000 # 查询数量
database = np.random.randn(nb, dim).astype('float32')
queries = np.random.randn(nq, dim).astype('float32')
# 1. 暴力搜索(基准,100% 召回)
index_flat = faiss.IndexFlatL2(dim)
t0 = time.time()
index_flat.add(database)
t_build_flat = time.time() - t0
t0 = time.time()
D_flat, I_flat = index_flat.search(queries, 10)
t_search_flat = time.time() - t0
# 2. IVF 倒排索引(粗量化,训练 + 检索)
nlist = 1000
quantizer = faiss.IndexFlatL2(dim)
index_ivf = faiss.IndexIVFFlat(quantizer, dim, nlist)
t0 = time.time()
index_ivf.train(database)
index_ivf.add(database)
t_build_ivf = time.time() - t0
index_ivf.nprobe = 10
t0 = time.time()
D_ivf, I_ivf = index_ivf.search(queries, 10)
t_search_ivf = time.time() - t0
# 3. HNSW 图索引(最高召回率)
index_hnsw = faiss.IndexHNSWFlat(dim, 32)
t0 = time.time()
index_hnsw.add(database)
t_build_hnsw = time.time() - t0
t0 = time.time()
D_hnsw, I_hnsw = index_hnsw.search(queries, 10)
t_search_hnsw = time.time() - t0
# 召回率计算
def recall(pred, truth):
return sum(len(set(p) & set(t)) for p, t in zip(pred, truth)) / (len(pred) * 10)
print(f"{'方法':<20} {'构建':<10} {'查询':<10} {'召回@10'}")
print(f"{'FlatL2 (暴力)':<20} {t_build_flat:.1f}s {t_search_flat:.3f}s 100%")
print(f"{'IVF (nlist=1000)':<20} {t_build_ivf:.1f}s {t_search_ivf:.3f}s {recall(I_ivf,I_flat):.0%}")
print(f"{'HNSW (M=32)':<20} {t_build_hnsw:.1f}s {t_search_hnsw:.3f}s {recall(I_hnsw,I_flat):.0%}")
# 典型结果:IVF 查询快 50x, HNSW 查询快 250x, 召回率 >95%
排序是最基础的算法操作之一。有序数据让搜索、去重、范围查询变得高效。理解排序算法不仅是学习其他算法的基础,更是理解"算法设计思想"的绝佳入口。
你有一副打乱的扑克牌,要按从小到大排好。冒泡排序——每次比较相邻两张,把大的往后挪,像气泡上浮。插入排序——一张一张拿起来,插到前面已排好的牌的正确位置。归并排序——把牌分成两半,分别排好,再合并。快速排序——选一张牌当基准,比它小的放左边,大的放右边,再分别排。
突破 O(n log n) 下限的排序算法——利用数据的特殊性质:
| 算法 | 平均 | 最坏 | 空间 | 稳定 |
|---|---|---|---|---|
| 冒泡排序 | 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) | ❌ |
# 按多个条件排序
data.sort(key=lambda x: (-x['score'], x['name']))
# 部分排序:只取前 K 个
import heapq
top_k = heapq.nsmallest(k, data, key=lambda x: -x['score'])
# 排序稳定性:相同值保持原始顺序
# Python 的 sort 是稳定的,可以用来做多关键字排序import random
# 1. 快速排序(实践中最快)
def quicksort(arr):
if len(arr) <= 1: return arr
pivot = arr[random.randint(0, len(arr)-1)] # 随机选 pivot
left = [x for x in arr if x < pivot]
mid = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quicksort(left) + mid + quicksort(right)
# 2. 归并排序(稳定,适合链表)
def merge_sort(arr):
if len(arr) <= 1: return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
result, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i]); i += 1
else:
result.append(right[j]); j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
# 3. 堆排序(原地,O(1) 空间)
def heap_sort(arr):
import heapq
heapq.heapify(arr)
return [heapq.heappop(arr) for _ in range(len(arr))]
# 4. 计数排序(O(n+k),整数专用)
def counting_sort(arr, k=None):
if not arr: return arr
if k is None: k = max(arr) + 1
count = [0] * k
for x in arr: count[x] += 1
result = []
for i in range(k):
result.extend([i] * count[i])
return result
# 5. 基数排序(大整数/字符串)
def radix_sort(arr):
if not arr: return arr
max_val = max(arr)
exp = 1
while max_val // exp > 0:
buckets = [[] for _ in range(10)]
for x in arr:
buckets[(x // exp) % 10].append(x)
arr = [x for bucket in buckets for x in bucket]
exp *= 10
return arr
# 对比测试
import time
data = [random.randint(0, 10000) for _ in range(10000)]
for name, func in [("快排", quicksort), ("归并", merge_sort), ("堆排", heap_sort)]:
d = data[:]
t0 = time.time()
func(d)
print(f"{name}: {time.time()-t0:.3f}s")
# Python 内置 sorted() 底层是 TimSort(归并+插入混合),通常最快
搜索算法的核心问题:给定一个目标,在数据集合中找到它。看似简单,但搜索效率的差异可以是 O(n) 和 O(log n) 的天壤之别。
你在通讯录里找一个人。线性搜索——从第一个开始,一个一个往下看。二分查找——通讯录已按字母排序,你先翻到中间,判断目标在前半还是后半,再对那一半重复。1000 人的通讯录,线性搜索最多看 1000 人,二分查找最多看 10 人。
从头到尾逐个检查。O(n)。适用于无序数据。
在有序数组上工作。每次把搜索范围缩小一半。
# 经典错误:整数溢出
mid = (left + right) // 2 # 安全
# mid = left + (right - left) // 2 # 更安全(某些语言需要)
# 经典错误:边界条件
# 是 left <= right 还是 left < right?
# 是 right = mid 还是 right = mid - 1?
# 取决于你用的是闭区间 [left, right] 还是左闭右开 [left, right)import bisect
# 1. 标准二分查找
def binary_search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = (lo + hi) // 2
if arr[mid] == target: return mid
elif arr[mid] < target: lo = mid + 1
else: hi = mid - 1
return -1
# 2. 查找左边界(第一个 >= target 的位置)
def lower_bound(arr, target):
lo, hi = 0, len(arr)
while lo < hi:
mid = (lo + hi) // 2
if arr[mid] < target: lo = mid + 1
else: hi = mid
return lo
# 3. 查找右边界(第一个 > target 的位置)
def upper_bound(arr, target):
lo, hi = 0, len(arr)
while lo < hi:
mid = (lo + hi) // 2
if arr[mid] <= target: lo = mid + 1
else: hi = mid
return lo
# 4. 旋转排序数组搜索
def search_rotated(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target: return mid
if nums[lo] <= nums[mid]: # 左半边有序
if nums[lo] <= target < nums[mid]: hi = mid - 1
else: lo = mid + 1
else: # 右半边有序
if nums[mid] < target <= nums[hi]: lo = mid + 1
else: hi = mid - 1
return -1
# 5. Python bisect 模块
arr = [1, 3, 3, 3, 5, 7, 9]
print(f"bisect_left(3) = {bisect.bisect_left(arr, 3)}") # 1
print(f"bisect_right(3) = {bisect.bisect_right(arr, 3)}") # 4
print(f"3 的个数 = {bisect.bisect_right(arr, 3) - bisect.bisect_left(arr, 3)}") # 3
# 6. 二分搜索应用:找第 K 小
def kth_smallest(matrix, k):
"""在 n×n 有序矩阵中找第 K 小的元素"""
n = len(matrix)
lo, hi = matrix[0][0], matrix[n-1][n-1]
while lo < hi:
mid = (lo + hi) // 2
count = sum(bisect.bisect_right(row, mid) for row in matrix)
if count < k: lo = mid + 1
else: hi = mid
return lo
分治法(Divide and Conquer)是最重要的算法设计范式之一。核心思想:把大问题拆成小问题,分别解决,再合并结果。
你是一个公司 CEO,要统计全公司 10000 人的工资总和。你不会自己一个人加——你让 10 个部门经理各自统计自己部门的,再把 10 个数字加起来。每个部门经理又让 10 个小组长各自统计……这就是分治——分而治之。
分治算法的时间复杂度通常满足递推式:T(n) = aT(n/b) + O(n^d)
归并排序:T(n) = 2T(n/2) + O(n),a=2, b=2, d=1。a = b^d → O(n log n)。
二分查找:T(n) = T(n/2) + O(1),a=1, b=2, d=0。a = b^d → O(log n)。
# 1. 归并排序(分治典范)
def merge_sort(arr):
if len(arr) <= 1: return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i]); i += 1
else:
result.append(right[j]); j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
print(merge_sort([38, 27, 43, 3, 9, 82, 10])) # [3, 9, 10, 27, 38, 43, 82]
# 2. 快速幂
def fast_power(base, exp, mod=None):
"""O(log n) 计算 base^exp"""
result = 1
base = base % mod if mod else base
while exp > 0:
if exp % 2 == 1:
result = result * base
if mod: result %= mod
exp //= 2
base = base * base
if mod: base %= mod
return result
print(fast_power(2, 10)) # 1024
print(fast_power(2, 100, 10**9+7)) # 大数取模
# 3. 快速选择(找第 K 小)
import random
def quickselect(arr, k):
"""平均 O(n) 找第 K 小的元素"""
if len(arr) == 1: return arr[0]
pivot = random.choice(arr)
left = [x for x in arr if x < pivot]
mid = [x for x in arr if x == pivot]
right = [x for x in arr 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))
print(quickselect([3, 1, 4, 1, 5, 9, 2, 6], 3)) # 2
# 4. 矩阵快速幂(加速递推,O(log n))
import numpy as np
def matrix_power(M, n, mod=None):
"""矩阵快速幂:计算 M^n,O(d³ log n)(d = 矩阵维度)"""
d = len(M)
result = np.eye(d, dtype=int)
if mod is not None:
result = result % mod
base = np.array(M, dtype=int)
while n > 0:
if n % 2 == 1:
result = result @ base
if mod is not None: result = result % mod
base = base @ base
if mod is not None: base = base % mod
n //= 2
return result
def fib_matrix(n, mod=10**9+7):
"""
用矩阵快速幂计算第 n 个斐波那契数,O(log n)
核心公式: [F(n+1), F(n)] = [[1,1],[1,0]]^n @ [1, 0]
"""
if n <= 1: return n
M = [[1, 1], [1, 0]]
result = matrix_power(M, n, mod=mod)
return result[0][1] % mod
# 对比:递归 O(2^n) vs 迭代 O(n) vs 矩阵快速幂 O(log n)
import time
n = 100000
t0 = time.time()
f = fib_matrix(n, mod=10**9+7)
t1 = time.time()
print(f"fib({n}) mod 10⁹+7 = {f}")
print(f"矩阵快速幂 O(log n): {t1-t0:.6f}s")
# 线性迭代 O(n) 对比
t0 = time.time()
a, b = 0, 1
for _ in range(n):
a, b = b, (a + b) % (10**9+7)
t1 = time.time()
print(f"线性迭代 O(n): {t1-t0:.6f}s")
# 矩阵快速幂在 n 极大时优势明显
贪心算法的核心思想:每一步都做当前看起来最好的选择,不考虑未来。听起来很短视,但在很多问题上,局部最优就是全局最优。
你在爬山,目标是爬到最高的山顶。贪心策略:每一步都往最高的方向走。如果这座山只有一个山顶(凸函数),贪心能带你到顶。但如果有很多山头(非凸),你可能困在一座矮山的山顶上。
0-1 背包问题不能用贪心——选性价比最高的物品不一定最优(可能剩余空间浪费)。需要动态规划。但分数背包可以贪心——可以拿物品的一部分。
# 活动选择问题
def activity_selection(activities):
"""选择最多不重叠活动。activities = [(start, end), ...]"""
activities.sort(key=lambda x: x[1]) # 按结束时间排序
selected = [activities[0]]
for s, e in activities[1:]:
if s >= selected[-1][1]: # 不重叠
selected.append((s, e))
return selected
# Huffman 编码
import heapq
from collections import Counter
def huffman_codes(text):
"""构建 Huffman 编码"""
freq = Counter(text)
heap = [[f, [c, ""]] for c, f in freq.items()]
heapq.heapify(heap)
while len(heap) > 1:
lo = heapq.heappop(heap)
hi = heapq.heappop(heap)
for pair in lo[1:]: pair[1] = '0' + pair[1]
for pair in hi[1:]: pair[1] = '1' + pair[1]
heapq.heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])
return {c: code for c, code in heap[0][1:]}
codes = huffman_codes("aabbcdddd")
for c, code in sorted(codes.items()):
print(f"'{c}': {code}")
# 分数背包(贪心)vs 0-1 背包(DP)
def fractional_knapsack(items, capacity):
"""分数背包:可以拿物品的一部分。贪心最优。"""
# 按性价比排序
items.sort(key=lambda x: x[1]/x[0], reverse=True)
total_value = 0
for weight, value in items:
if capacity >= weight:
total_value += value
capacity -= weight
else:
total_value += value * (capacity / weight)
break
return total_value
# 示例
items = [(10, 60), (20, 100), (30, 120)] # (重量, 价值)
print(f"分数背包最优: {fractional_knapsack(items, 50)}") # 240.0
# 0-1 背包不能用贪心,必须用 DP(见第 16 章)
动态规划(DP)是算法设计中最强大的武器之一。核心思想:把大问题拆成小问题,记住每个小问题的解,避免重复计算。和分治法的区别:DP 的子问题有重叠,分治的子问题不重叠。
你爬楼梯,每次可以走 1 步或 2 步。问走到第 10 阶有多少种走法。暴力方法:枚举所有路径。DP 思路:走到第 10 阆 = 从第 9 阆走 1 步 + 从第 8 阆走 2 步。所以 f(10) = f(9) + f(8)。你只需要记住 f(1) 到 f(9) 的值,不用重复计算。
| 问题 | 状态定义 | 转移方程 | 复杂度 |
|---|---|---|---|
| 斐波那契 | f(i) = 第 i 项 | f(i) = f(i-1) + f(i-2) | O(n) |
| 爬楼梯 | f(i) = 到第 i 阶方案数 | f(i) = f(i-1) + f(i-2) | O(n) |
| 0-1 背包 | dp(i,w) = 前 i 件容量 w 的最大价值 | max(选, 不选) | O(nW) |
| 最长公共子序列 | dp(i,j) = s1前i和s2前j的 LCS | 匹配/不匹配 | O(mn) |
| 编辑距离 | dp(i,j) = s1前i变s2前j的最少操作 | 增/删/改 | O(mn) |
① 定义状态(dp 数组的含义)→ ② 写转移方程 → ③ 确定初始条件 → ④ 确定遍历顺序 → ⑤ 确定返回值。最关键的一步是定义状态——状态定义对了,转移方程自然就出来了。
# 1. 斐波那契数列(记忆化 vs 制表)
from functools import lru_cache
# 自顶向下:记忆化
@lru_cache(maxsize=None)
def fib_memo(n):
if n <= 1: return n
return fib_memo(n-1) + fib_memo(n-2)
# 自底向上:制表
def fib_tab(n):
if n <= 1: return n
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
# 空间优化:只用两个变量
def fib_opt(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
# 2. 0-1 背包问题
def knapsack(weights, values, capacity):
n = len(weights)
# dp[i][w] = 前 i 件物品、容量 w 的最大价值
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(capacity + 1):
dp[i][w] = dp[i-1][w] # 不选第 i 件
if w >= weights[i-1]:
# 选第 i 件
dp[i][w] = max(dp[i][w],
dp[i-1][w - weights[i-1]] + values[i-1])
return dp[n][capacity]
# 空间优化:一维 DP
def knapsack_1d(weights, values, capacity):
dp = [0] * (capacity + 1)
for i in range(len(weights)):
for w in range(capacity, weights[i] - 1, -1): # 逆序!
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
return dp[capacity]
print(knapsack([2,3,4,5], [3,4,5,6], 8)) # 10
# 3. 编辑距离
def edit_distance(s1, s2):
m, n = len(s1), len(s2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1): dp[i][0] = i # 删除
for j in range(n + 1): dp[0][j] = j # 插入
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i-1] == s2[j-1]:
dp[i][j] = dp[i-1][j-1] # 字符相同,不用操作
else:
dp[i][j] = 1 + min(
dp[i-1][j], # 删除
dp[i][j-1], # 插入
dp[i-1][j-1] # 替换
)
return dp[m][n]
print(edit_distance("kitten", "sitting")) # 3
回溯法是一种系统地搜索所有可能解的方法——走不通就回头,换条路继续试。它是暴力搜索的"升级版",通过剪枝大幅减少搜索空间。
你在一个迷宫里找出口。每到一个岔路口,你选一条路走。如果走到死胡同,你退回到上一个岔路口,选另一条路。这就是回溯——试探 + 回退 + 换路。
def backtrack(路径, 选择列表):
if 满足结束条件:
result.append(路径.copy())
return
for 选择 in 选择列表:
if 不满足约束条件: # 剪枝
continue
做选择 # 把选择加入路径
backtrack(路径, 选择列表)
撤销选择 # 回溯,把选择从路径中移除
回溯是"试了才知道行不行",DP 是"算过了就记住"。回溯适合求所有解(排列、组合、子集),DP 适合求最优解(最大值、最小值、方案数)。如果问题有大量重叠子问题,用 DP;如果需要枚举所有可能,用回溯。
# 1. 全排列
def permute(nums):
result = []
def backtrack(path, used):
if len(path) == len(nums):
result.append(path[:]); return
for i in range(len(nums)):
if used[i]: continue
used[i] = True
path.append(nums[i])
backtrack(path, used)
path.pop()
used[i] = False
backtrack([], [False]*len(nums))
return result
# 2. 子集
def subsets(nums):
result = []
def backtrack(start, path):
result.append(path[:])
for i in range(start, len(nums)):
path.append(nums[i])
backtrack(i+1, path)
path.pop()
backtrack(0, [])
return result
# 3. 组合总和(可重复使用)
def combinationSum(candidates, target):
result = []
candidates.sort()
def backtrack(start, path, remain):
if remain == 0:
result.append(path[:]); return
for i in range(start, len(candidates)):
if candidates[i] > remain: break
path.append(candidates[i])
backtrack(i, path, remain - candidates[i])
path.pop()
backtrack(0, [], target)
return result
# 4. N 皇后
def solveNQueens(n):
result = []
def backtrack(row, cols, diag1, diag2, board):
if row == n:
result.append([''.join(r) for r in board]); return
for col in range(n):
if col in cols or row-col in diag1 or row+col in diag2:
continue
board[row][col] = 'Q'
backtrack(row+1, cols|{col}, diag1|{row-col}, diag2|{row+col}, board)
board[row][col] = '.'
backtrack(0, set(), set(), set(), [['.']*n for _ in range(n)])
return result
# 5. 括号生成
def generateParenthesis(n):
result = []
def backtrack(path, left, right):
if len(path) == 2*n:
result.append(path); return
if left < n: backtrack(path+'(', left+1, right)
if right < left: backtrack(path+')', left, right+1)
backtrack('', 0, 0)
return result
# 测试
print(f"全排列 [1,2,3]: {permute([1,2,3])}")
print(f"子集 [1,2,3]: {subsets([1,2,3])}")
print(f"组合总和 [2,3,6,7] target=7: {combinationSum([2,3,6,7], 7)}")
print(f"4皇后解数: {len(solveNQueens(4))}") # 2
print(f"3对括号: {generateParenthesis(3)}")
很多 AI 问题可以抽象为"在状态空间中搜索":游戏 AI 找最佳走法、机器人规划路径、解谜题找到答案。本章介绍解决这类问题的核心算法。
你在玩一个迷宫游戏。每一步你有多个选择(上下左右),每种选择带你到一个新状态(新位置)。你要从起点找到终点的最优路径。A* 搜索就是"先走看起来离终点最近的方向"。
A* 是最常用的启发式搜索算法,结合了 Dijkstra(保证最优)和贪心搜索(速度快)的优点。
用于两人零和博弈(棋类游戏)。假设对手总是选择对你最不利的走法。
MCTS 通过随机模拟来评估每个走法的价值,不需要显式的评估函数。
import heapq
def a_star(graph, start, goal, heuristic):
"""
A* 搜索
graph: {node: [(neighbor, cost), ...]}
heuristic: h(node) → 估计到终点的距离
"""
open_set = [(0, start)] # (f值, 节点)
came_from = {}
g_score = {start: 0} # 起点到当前的实际代价
f_score = {start: heuristic(start)} # g + h
closed_set = set()
while open_set:
_, current = heapq.heappop(open_set)
if current == goal:
# 回溯路径
path = [current]
while current in came_from:
current = came_from[current]
path.append(current)
return path[::-1]
closed_set.add(current)
for neighbor, cost in graph[current]:
if neighbor in closed_set:
continue
tentative_g = g_score[current] + cost
if tentative_g < g_score.get(neighbor, float('inf')):
came_from[neighbor] = current
g_score[neighbor] = tentative_g
f_score[neighbor] = tentative_g + heuristic(neighbor)
heapq.heappush(open_set, (f_score[neighbor], neighbor))
return None # 无路径
# 示例:网格地图寻路
def manhattan_distance(goal):
return lambda pos: abs(pos[0] - goal[0]) + abs(pos[1] - goal[1])
# 简单图
graph = {
'A': [('B', 1), ('C', 4)],
'B': [('A', 1), ('C', 2), ('D', 5)],
'C': [('A', 4), ('B', 2), ('D', 1)],
'D': [('B', 5), ('C', 1)]
}
h = lambda n: {'A': 3, 'B': 2, 'C': 1, 'D': 0}[n]
path = a_star(graph, 'A', 'D', h)
print(f"最短路径: {path}") # A → B → C → D
import math
import random
class MCTSNode:
def __init__(self, state, parent=None):
self.state = state
self.parent = parent
self.children = []
self.wins = 0
self.visits = 0
def ucb1(self, c=1.41):
"""UCB1 公式:平衡利用和探索"""
if self.visits == 0:
return float('inf')
return self.wins / self.visits + c * math.sqrt(
math.log(self.parent.visits) / self.visits)
def best_child(self):
return max(self.children, key=lambda c: c.ucb1())
def mcts_search(root, n_iterations=1000):
"""MCTS 主循环"""
for _ in range(n_iterations):
node = root
# 1. 选择:沿 UCB1 最大的子节点下降
while node.children and not is_terminal(node.state):
node = node.best_child()
# 2. 扩展:如果是非终止状态,添加子节点
if not is_terminal(node.state) and node.visits > 0:
for action in get_legal_actions(node.state):
child_state = apply_action(node.state, action)
child = MCTSNode(child_state, parent=node)
node.children.append(child)
node = random.choice(node.children)
# 3. 模拟:随机走棋到终局
result = simulate_random(node.state)
# 4. 回传:沿路径更新统计
while node is not None:
node.visits += 1
node.wins += result
node = node.parent
# 返回访问次数最多的子节点(最稳健的选择)
return max(root.children, key=lambda c: c.visits).state
import math, random
from copy import deepcopy
class TicTacToe:
"""完整井字棋环境:MCTS 最小可运行示例"""
def __init__(self):
self.board = [0] * 9 # 0=空, 1=X, -1=O
self.current_player = 1
def clone(self):
env = TicTacToe()
env.board = self.board[:]
env.current_player = self.current_player
return env
def get_legal_actions(self):
return [i for i in range(9) if self.board[i] == 0]
def step(self, action):
self.board[action] = self.current_player
self.current_player *= -1
def is_terminal(self):
return self.get_winner() is not None or not self.get_legal_actions()
def get_winner(self):
lines = [[0,1,2],[3,4,5],[6,7,8],[0,3,6],[1,4,7],[2,5,8],[0,4,8],[2,4,6]]
for a,b,c in lines:
if self.board[a] and self.board[a] == self.board[b] == self.board[c]:
return self.board[a]
return None
def get_reward(self, player):
"""从 player 视角返回奖励"""
winner = self.get_winner()
if winner == player: return 1
if winner == -player: return -1
return 0 # 平局
def display(self):
symbols = {0: '.', 1: 'X', -1: 'O'}
for i in range(3):
print(' '.join(symbols[self.board[i*3+j]] for j in range(3)))
print()
# MCTS + 井字棋
class MCTSNode:
def __init__(self, env, parent=None, action=None):
self.env = env
self.parent = parent
self.action = action
self.children = []
self.wins = 0
self.visits = 0
self.untried_actions = env.get_legal_actions()
def ucb1(self, c=1.41):
if self.visits == 0: return float('inf')
return self.wins/self.visits + c*math.sqrt(math.log(self.parent.visits)/self.visits)
def best_child(self):
return max(self.children, key=lambda c: c.ucb1())
def mcts_tictactoe(root_env, n_simulations=1000):
root = MCTSNode(root_env.clone())
root_player = root_env.current_player
for _ in range(n_simulations):
node = root
# 选择
while not node.untried_actions and node.children:
node = node.best_child()
# 扩展
if node.untried_actions:
action = node.untried_actions.pop()
child_env = node.env.clone()
child_env.step(action)
child = MCTSNode(child_env, parent=node, action=action)
node.children.append(child)
node = child
# 模拟
sim_env = node.env.clone()
while not sim_env.is_terminal():
action = random.choice(sim_env.get_legal_actions())
sim_env.step(action)
# 回传
reward = sim_env.get_reward(root_player)
while node is not None:
node.visits += 1
node.wins += reward
reward = -reward # 交替胜负
node = node.parent
return max(root.children, key=lambda c: c.visits).action
# 运行:AI 自己跟自己下棋
env = TicTacToe()
print("MCTS 井字棋:AI vs AI\n")
while not env.is_terminal():
action = mcts_tictactoe(env, n_simulations=1000)
player_name = 'X' if env.current_player == 1 else 'O'
print(f"玩家 {player_name} 选择位置 {action}")
env.step(action)
env.display()
winner = env.get_winner()
if winner: print(f"{'X' if winner==1 else 'O'} 获胜!")
else: print("平局!")
AI 处理的核心数据就是文本。从 Tokenizer 到搜索引擎,从 DNA 比对到拼写检查,字符串算法无处不在。
你在一本厚书里找"人工智能"四个字。暴力搜索——从第一个字开始,逐字比较。KMP——如果匹配失败,利用已匹配的信息跳过不可能的位置。Rabin-Karp——先把目标词算一个"指纹",然后在书里滑动窗口算指纹,指纹匹配了再逐字确认。
Knuth-Morris-Pratt 算法利用匹配失败时已掌握的信息,避免回退。核心是 next 数组(也叫失败函数)。
Trie 是一种树形数据结构,用于高效存储和查找字符串集合。
def kmp_search(text, pattern):
"""KMP 字符串匹配"""
def build_next(pattern):
"""构建 next 数组(失败函数)"""
n = len(pattern)
next_arr = [0] * n
j = 0
for i in range(1, n):
while j > 0 and pattern[i] != pattern[j]:
j = next_arr[j - 1] # 回退
if pattern[i] == pattern[j]:
j += 1
next_arr[i] = j
return next_arr
next_arr = build_next(pattern)
j = 0 # 模式串指针
results = []
for i in range(len(text)): # 主串指针不回退
while j > 0 and text[i] != pattern[j]:
j = next_arr[j - 1] # 利用 next 数组跳转
if text[i] == pattern[j]:
j += 1
if j == len(pattern):
results.append(i - j + 1) # 找到匹配
j = next_arr[j - 1]
return results
# 示例
text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
print(f"匹配位置: {kmp_search(text, pattern)}") # [9]
# next 数组解读
# pattern: A B A B C A B A B
# next: 0 0 1 2 0 1 2 3 4
# 含义:位置 i 的最长相等前后缀长度
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
self.count = 0 # 词频
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end = True
node.count += 1
def search(self, word):
node = self.root
for char in word:
if char not in node.children:
return False
node = node.children[char]
return node.is_end
def autocomplete(self, prefix, max_results=5):
"""自动补全:返回以 prefix 开头的所有单词"""
node = self.root
for char in prefix:
if char not in node.children:
return []
node = node.children[char]
# DFS 收集所有以 prefix 开头的单词
results = []
self._dfs(node, prefix, results, max_results)
return results
def _dfs(self, node, path, results, limit):
if len(results) >= limit:
return
if node.is_end:
results.append((path, node.count))
for char, child in sorted(node.children.items()):
self._dfs(child, path + char, results, limit)
# 示例:搜索引擎自动补全
trie = Trie()
words = ["python", "pytorch", "pandas", "numpy", "neural",
"network", "natural", "language", "learning", "loss"]
for w in words:
trie.insert(w)
print(trie.autocomplete("py")) # [('python', 1), ('pytorch', 1)]
print(trie.autocomplete("ne")) # [('neural', 1), ('network', 1), ('natural', 1)]
print(trie.autocomplete("l")) # [('language', 1), ('learning', 1), ('loss', 1)]
def simple_bpe(text, num_merges=10):
"""BPE:GPT Tokenizer 的核心算法"""
# 初始:每个字符是一个 token
tokens = list(text.encode('utf-8'))
vocab = {bytes([i]): i for i in range(256)}
for i in range(num_merges):
# 统计相邻 pair 的频率
pair_counts = {}
for j in range(len(tokens) - 1):
pair = (tokens[j], tokens[j + 1])
pair_counts[pair] = pair_counts.get(pair, 0) + 1
if not pair_counts:
break
# 找最频繁的 pair
best_pair = max(pair_counts, key=pair_counts.get)
new_token = 256 + i
# 合并所有出现的 pair
new_tokens = []
j = 0
while j < len(tokens):
if j < len(tokens) - 1 and (tokens[j], tokens[j+1]) == best_pair:
new_tokens.append(new_token)
j += 2
else:
new_tokens.append(tokens[j])
j += 1
tokens = new_tokens
print(f"合并 {i+1}: {best_pair} → {new_token}, 词表大小: {256 + i + 1}")
return tokens
# 示例
text = "the cat sat on the mat the cat"
tokens = simple_bpe(text, num_merges=5)
print(f"原始字符数: {len(text)}, BPE token 数: {len(tokens)}")
class BPETokenizer:
"""完整 BPE Tokenizer:训练 → 编码 → 解码"""
def __init__(self):
self.merges = {} # 合并规则: (token_a, token_b) → merged_token
self.vocab = {} # token → id
self.inv_vocab = {} # id → token
def train(self, text, vocab_size=300):
"""训练 BPE:学习合并规则"""
# 初始词表:所有单字节
tokens = list(text.encode('utf-8'))
self.vocab = {bytes([i]): i for i in range(256)}
num_merges = vocab_size - 256
for i in range(num_merges):
# 统计相邻 pair 频率
pair_counts = {}
for j in range(len(tokens) - 1):
pair = (tokens[j], tokens[j+1])
pair_counts[pair] = pair_counts.get(pair, 0) + 1
if not pair_counts: break
best_pair = max(pair_counts, key=pair_counts.get)
new_token = 256 + i
self.merges[best_pair] = new_token
# 执行合并
new_tokens = []
j = 0
while j < len(tokens):
if j < len(tokens)-1 and (tokens[j], tokens[j+1]) == best_pair:
new_tokens.append(new_token)
j += 2
else:
new_tokens.append(tokens[j])
j += 1
tokens = new_tokens
# 构建完整词表
for token_id in set(tokens):
self.vocab[f"tok_{token_id}"] = token_id
self.inv_vocab = {v: k for k, v in self.vocab.items()}
def encode(self, text):
"""编码:文本 → token ID 列表"""
tokens = list(text.encode('utf-8'))
while len(tokens) > 1:
# 找可以合并的 pair
min_pair = None
min_rank = float('inf')
for j in range(len(tokens) - 1):
pair = (tokens[j], tokens[j+1])
if pair in self.merges:
rank = self.merges[pair]
if rank < min_rank:
min_rank = rank
min_pair = (j, pair)
if min_pair is None: break
j, pair = min_pair
tokens = tokens[:j] + [self.merges[pair]] + tokens[j+2:]
return tokens
def decode(self, ids):
"""解码:token ID 列表 → 文本"""
raw = b''
for token_id in ids:
if token_id < 256:
raw += bytes([token_id])
else:
# 合并的 token 需要递归解码
raw += f"[{token_id}]".encode()
try:
return raw.decode('utf-8', errors='replace')
except:
return str(ids)
# 示例
tokenizer = BPETokenizer()
text = "the cat sat on the mat " * 100
tokenizer.train(text, vocab_size=280)
encoded = tokenizer.encode("the cat on the mat")
print(f"编码: {encoded}")
print(f"压缩比: {len('the cat on the mat')}/{len(encoded)} = {len('the cat on the mat')/len(encoded):.1f}x")
编码和压缩算法的目标:用更少的比特表示同样的信息。在 AI 中,这不仅关乎存储效率,更关乎模型大小和推理速度。
你发短信时用缩写:"今天下午三点见" → "天3见"。你用更少的字传达了同样的信息。编码压缩算法做的就是这件事——找到信息的"缩写"。
出现频率高的字符用短编码,频率低的用长编码。
信息熵 H = -Σ p(x) log₂ p(x)。霍夫曼编码的平均码长接近信息熵,是最优前缀编码。
比霍夫曼更高效——把整个消息编码为一个 [0,1) 区间内的实数。接近信息熵极限。
import heapq
from collections import Counter
class HuffmanNode:
def __init__(self, char=None, freq=0, left=None, right=None):
self.char = char
self.freq = freq
self.left = left
self.right = right
def __lt__(self, other):
return self.freq < other.freq
def build_huffman(text):
"""构建霍夫曼编码"""
# 1. 统计频率
freq = Counter(text)
# 2. 构建优先队列
heap = [HuffmanNode(char, f) for char, f in freq.items()]
heapq.heapify(heap)
# 3. 构建霍夫曼树
while len(heap) > 1:
left = heapq.heappop(heap)
right = heapq.heappop(heap)
parent = HuffmanNode(freq=left.freq + right.freq, left=left, right=right)
heapq.heappush(heap, parent)
# 4. 生成编码表
codes = {}
def traverse(node, code=""):
if node.char is not None:
codes[node.char] = code if code else "0"
return
traverse(node.left, code + "0")
traverse(node.right, code + "1")
traverse(heap[0])
return codes
# 示例
text = "aabbcdddd" * 100
codes = build_huffman(text)
print("霍夫曼编码:")
for char, code in sorted(codes.items()):
print(f" '{char}': {code}")
# 压缩率
original_bits = len(text) * 8
compressed_bits = sum(len(codes[c]) for c in text)
print(f"原始: {original_bits} bits, 压缩后: {compressed_bits} bits")
print(f"压缩率: {compressed_bits/original_bits:.1%}")
算术编码把整个消息编码为一个 [0,1) 区间的实数。与霍夫曼编码不同,它不受"每个字符必须用整数个比特"的限制,能更接近信息熵极限。
from collections import Counter
def arithmetic_encode(text):
"""算术编码:把整个字符串编码为一个 [0,1) 区间内的数"""
# 1. 统计频率,构建概率区间
freq = Counter(text)
total = len(text)
# 区间: {char: (low, high)}
low = 0.0
intervals = {}
for char, count in sorted(freq.items()):
high = low + count / total
intervals[char] = (low, high)
low = high
# 2. 编码:逐步缩小区间
lo, hi = 0.0, 1.0
for char in text:
range_width = hi - lo
char_lo, char_hi = intervals[char]
hi = lo + range_width * char_hi
lo = lo + range_width * char_lo
# 3. 返回区间中点作为编码
return (lo + hi) / 2, intervals, len(text)
def arithmetic_decode(code, intervals, length):
"""算术编码解码"""
# 反向构建字符查找表
sorted_chars = sorted(intervals.items(), key=lambda x: x[1][0])
lo, hi = 0.0, 1.0
result = []
for _ in range(length):
range_width = hi - lo
# 找到 code 落在哪个字符的区间
for char, (char_lo, char_hi) in sorted_chars:
new_lo = lo + range_width * char_lo
new_hi = lo + range_width * char_hi
if new_lo <= code < new_hi:
result.append(char)
lo, hi = new_lo, new_hi
break
return ''.join(result)
# 示例
text = "aabbcdddd"
code, intervals, length = arithmetic_encode(text)
print(f"原文: {text}")
print(f"编码: {code}")
print(f"解码: {arithmetic_decode(code, intervals, length)}")
print(f"信息熵: {-sum((c/len(text)) * np.log2(c/len(text)) for c in Counter(text).values()):.3f} bits/char")
LZ77 是 gzip 的基础算法。核心思想:用 (距离, 长度) 引用前面出现过的重复内容。距离 = 回溯多远,长度 = 重复多长。不需要预扫描数据,适合流式压缩。
def lz77_compress(text, window_size=256):
"""LZ77 压缩:输出 (距离, 长度, 下一个字符) 三元组"""
tokens = []
pos = 0
while pos < len(text):
# 搜索窗口: [max(0, pos-window_size), pos)
search_start = max(0, pos - window_size)
best_dist = 0
best_len = 0
# 在搜索窗口内找最长匹配
for j in range(search_start, pos):
# 从位置 j 开始尝试匹配
match_len = 0
while (pos + match_len < len(text) and
text[j + match_len] == text[pos + match_len] and
match_len < window_size):
match_len += 1
if match_len > best_len:
best_len = match_len
best_dist = pos - j
# 下一个字符
if pos + best_len < len(text):
next_char = text[pos + best_len]
else:
next_char = ''
tokens.append((best_dist, best_len, next_char))
pos += best_len + 1
return tokens
def lz77_decompress(tokens):
"""LZ77 解压"""
result = []
for dist, length, char in tokens:
# 从已解压的结果中回溯复制
start = len(result) - dist
for i in range(length):
result.append(result[start + i])
if char:
result.append(char)
return ''.join(result)
# 示例
text = "ABABABABABABCDABABABCD"
tokens = lz77_compress(text, window_size=256)
decompressed = lz77_decompress(tokens)
print(f"原文: {text} ({len(text)} 字符)")
print(f"压缩: {tokens} ({len(tokens)} 个三元组)")
print(f"解压: {decompressed}")
print(f"正确: {text == decompressed}")
# 对比压缩率
print(f"\n原始: {len(text) * 8} bits (每字符 8 bit)")
print(f"压缩: {len(tokens) * 24} bits (每个三元组 ~24 bit)")
print(f"压缩率: {len(tokens) * 24 / (len(text) * 8):.1%}")
传统的机器学习是"先收集数据,再训练模型"。但在很多场景中,数据是逐步到来的,你必须边学边决策。这就是在线学习——在不确定中边探索边利用。
你第一次去一个美食广场,有 10 家店。你不知道哪家好吃。探索:每家都试一遍。利用:只去最好吃的那家。但你试的次数有限,而且口味可能变化。怎么分配"试新店"和"去老店"的比例?这就是多臂赌博机(MAB)问题。
import numpy as np
class EpsilonGreedy:
def __init__(self, n_arms, epsilon=0.1):
self.n_arms = n_arms
self.epsilon = epsilon
self.counts = np.zeros(n_arms) # 每个臂被拉的次数
self.values = np.zeros(n_arms) # 每个臂的平均奖励
def select_arm(self):
if np.random.random() < self.epsilon:
return np.random.randint(self.n_arms) # 探索
return np.argmax(self.values) # 利用
def update(self, arm, reward):
self.counts[arm] += 1
n = self.counts[arm]
# 增量更新平均值
self.values[arm] += (reward - self.values[arm]) / n
# 模拟:10 个臂,真实概率不同
np.random.seed(42)
true_probs = np.random.uniform(0.1, 0.9, 10)
agent = EpsilonGreedy(10, epsilon=0.1)
total_reward = 0
for t in range(10000):
arm = agent.select_arm()
reward = np.random.binomial(1, true_probs[arm])
agent.update(arm, reward)
total_reward += reward
print(f"最优臂: {np.argmax(true_probs)}, 选中最多: {np.argmax(agent.counts)}")
print(f"总奖励: {total_reward}/10000")
class UCB:
"""上置信界算法:乐观面对不确定性"""
def __init__(self, n_arms):
self.n_arms = n_arms
self.counts = np.zeros(n_arms)
self.values = np.zeros(n_arms)
self.t = 0
def select_arm(self):
self.t += 1
# 先确保每个臂至少被拉一次
for i in range(self.n_arms):
if self.counts[i] == 0:
return i
# UCB 公式:均值 + 探索奖励
ucb_values = self.values + np.sqrt(2 * np.log(self.t) / self.counts)
return np.argmax(ucb_values)
def update(self, arm, reward):
self.counts[arm] += 1
n = self.counts[arm]
self.values[arm] += (reward - self.values[arm]) / n
Thompson 采样是最优雅的探索-利用策略:为每个臂维护一个 Beta 分布(成功次数 α,失败次数 β),每次从每个臂的分布中采样,选采样值最大的臂。效果通常优于 ε-Greedy 和 UCB。
它天然实现了"不确定性越大,探索概率越高"。如果一个臂的 α 和 β 都很小(尝试少),它的 Beta 分布很宽,采样值可能很高也可能很低——自然产生探索。随着尝试次数增加,分布变窄,采样值趋于稳定——自然转向利用。不需要手动调衰减参数。
class ThompsonSampling:
"""Thompson 采样:贝叶斯方法,实践中效果最好"""
def __init__(self, n_arms):
self.n_arms = n_arms
self.alpha = np.ones(n_arms) # 成功次数(先验 = 1)
self.beta = np.ones(n_arms) # 失败次数(先验 = 1)
def select_arm(self):
# 从每个臂的 Beta 分布中采样,选最大的
samples = np.random.beta(self.alpha, self.beta)
return np.argmax(samples)
def update(self, arm, reward):
# reward 为 1 表示成功,0 表示失败
if reward > 0:
self.alpha[arm] += 1
else:
self.beta[arm] += 1
# 统一实验框架:对比 ε-Greedy、UCB、Thompson Sampling
np.random.seed(42)
n_arms = 10
n_rounds = 10000
true_probs = np.random.uniform(0.1, 0.9, n_arms)
best_arm = np.argmax(true_probs)
strategies = {
"ε-Greedy (ε=0.1)": EpsilonGreedy(n_arms, epsilon=0.1),
"UCB": UCB(n_arms),
"Thompson Sampling": ThompsonSampling(n_arms),
}
results = {}
for name, agent in strategies.items():
# 重置随机种子保证公平
np.random.seed(42)
total_reward = 0
optimal_pulls = 0
for t in range(n_rounds):
arm = agent.select_arm()
reward = np.random.binomial(1, true_probs[arm])
agent.update(arm, reward)
total_reward += reward
if arm == best_arm:
optimal_pulls += 1
regret = n_rounds * true_probs[best_arm] - total_reward
results[name] = {
"总奖励": total_reward,
"最优臂选择率": f"{optimal_pulls/n_rounds:.1%}",
"累积遗憾": f"{regret:.0f}",
}
print(f"{name}: 奖励={total_reward}, 最优臂={optimal_pulls/n_rounds:.1%}, 遗憾={regret:.0f}")
print(f"\n最优臂真实概率: {true_probs[best_arm]:.3f}")
有些问题用确定性算法很难高效解决,但加入随机性后就变得简单。随机化算法利用随机数来指导计算,在效率和正确性之间取得巧妙平衡。
你在一堆干草里找一根针。确定性方法:一根一根检查。随机化方法:随机抓一把,看有没有针。如果针的比例不太低,随机抓几次就能找到。这就是随机化——用"可能错"换"快很多"。
import random
def reservoir_sampling(stream, k):
"""从流中均匀采样 k 个元素"""
reservoir = []
for i, item in enumerate(stream):
if i < k:
reservoir.append(item)
else:
j = random.randint(0, i)
if j < k:
reservoir[j] = item
return reservoirimport random
# 1. 随机化快速排序
def randomized_quicksort(arr):
if len(arr) <= 1: return arr
pivot = random.choice(arr)
left = [x for x in arr if x < pivot]
mid = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return randomized_quicksort(left) + mid + randomized_quicksort(right)
# 2. 蓄水池采样(流式数据)
def reservoir_sample(stream, k):
"""从未知大小的数据流中均匀采样 k 个"""
reservoir = []
for i, item in enumerate(stream):
if i < k:
reservoir.append(item)
else:
j = random.randint(0, i)
if j < k:
reservoir[j] = item
return reservoir
# 测试:从 10000 个数中采样 5 个
sample = reservoir_sample(range(10000), 5)
print(f"采样结果: {sample}") # 每次运行不同
# 3. 随机化蒙特卡洛估算 π
import math
def estimate_pi(n_samples=100000):
"""用蒙特卡洛方法估算 π"""
inside = 0
for _ in range(n_samples):
x, y = random.random(), random.random()
if x*x + y*y <= 1:
inside += 1
return 4 * inside / n_samples
print(f"估算 π ≈ {estimate_pi():.4f}") # ≈ 3.1416
# 4. Fisher-Yates 洗牌算法
def shuffle(arr):
"""原地随机洗牌:O(n)"""
for i in range(len(arr) - 1, 0, -1):
j = random.randint(0, i)
arr[i], arr[j] = arr[j], arr[i]
return arr
print(shuffle([1, 2, 3, 4, 5])) # 每次运行不同
在概率模型中,我们经常需要从复杂分布中采样,或者计算高维积分。精确计算往往不可行,采样算法用随机近似来解决这些问题。
你想知道一个不规则湖泊的面积。精确计算需要复杂的积分。但你可以往一个包含湖泊的矩形里随机撒 10000 颗豆子,数有多少颗落在湖里。比例 × 矩形面积 ≈ 湖泊面积。这就是蒙特卡洛积分——用随机采样近似计算。
MCMC 构造一条马尔可夫链,使其平稳分布就是目标分布。
从一个容易采样的分布 q 中采样,用权重 w(x) = p(x)/q(x) 修正偏差。用于估计 E_p[f(x)]。
import numpy as np
def metropolis_hastings(log_target, proposal, x0, n_samples=10000):
"""
MH 采样器
log_target: 目标分布的对数密度函数
proposal: 提议函数 proposal(x) → 新样本
x0: 初始值
"""
samples = [x0]
x = x0
accepted = 0
for _ in range(n_samples):
# 提议新状态
x_proposal = proposal(x)
# 计算接受概率
log_alpha = (log_target(x_proposal) - log_target(x))
# 接受/拒绝
if np.log(np.random.random()) < log_alpha:
x = x_proposal
accepted += 1
samples.append(x)
print(f"接受率: {accepted/n_samples:.2%}")
return np.array(samples)
# 示例:从混合高斯分布采样
def log_target(x):
# 0.3 * N(-2, 1) + 0.7 * N(3, 0.5²)
return np.log(
0.3 * np.exp(-0.5 * (x + 2)**2) +
0.7 * np.exp(-0.5 * ((x - 3) / 0.5)**2)
)
samples = metropolis_hastings(log_target, lambda x: x + np.random.randn(), 0.0)
print(f"样本均值: {samples[1000:].mean():.2f}") # ≈ 1.7
import numpy as np
def top_k_sampling(logits, k=50, temperature=1.0):
"""Top-K 采样:只从概率最高的 K 个 token 中采样"""
# 温度缩放
logits = logits / temperature
# 找到 top-k
top_k_indices = np.argsort(logits)[-k:]
top_k_logits = logits[top_k_indices]
# Softmax
probs = np.exp(top_k_logits - top_k_logits.max())
probs = probs / probs.sum()
# 采样
chosen_idx = np.random.choice(len(probs), p=probs)
return top_k_indices[chosen_idx]
def top_p_sampling(logits, p=0.9, temperature=1.0):
"""Top-P (Nucleus) 采样:累积概率超过 p 的最小集合"""
logits = logits / temperature
sorted_indices = np.argsort(logits)[::-1]
sorted_logits = logits[sorted_indices]
probs = np.exp(sorted_logits - sorted_logits.max())
probs = probs / probs.sum()
# 找到累积概率超过 p 的位置
cumsum = np.cumsum(probs)
cutoff = np.searchsorted(cumsum, p) + 1
# 只在 cutoff 内采样
top_indices = sorted_indices[:cutoff]
top_probs = probs[:cutoff]
top_probs = top_probs / top_probs.sum()
return top_indices[np.random.choice(len(top_probs), p=top_probs)]
# 示例
logits = np.random.randn(50000) # 50000 个 token 的 logits
token = top_p_sampling(logits, p=0.9, temperature=0.7)
import torch
import torch.nn.functional as F
def batch_sample(logits, temperature=1.0, top_k=0, top_p=1.0):
"""
GPU 批量采样:处理 [batch_size, vocab_size] 的 logits
支持 Temperature、Top-K、Top-P 组合
"""
# 温度缩放(处理趋近 0 的数值稳定性)
if temperature < 1e-6:
return logits.argmax(dim=-1) # 退化为 greedy
logits = logits / temperature
# Top-K 截断
if top_k > 0:
top_k = min(top_k, logits.size(-1))
indices_to_remove = logits < torch.topk(logits, top_k)[0][..., -1, None]
logits[indices_to_remove] = float('-inf')
# Top-P (Nucleus) 截断
if top_p < 1.0:
sorted_logits, sorted_indices = torch.sort(logits, descending=True)
cumulative_probs = torch.cumsum(F.softmax(sorted_logits, dim=-1), dim=-1)
# 找到累积概率超过 p 的位置
sorted_mask = cumulative_probs - F.softmax(sorted_logits, dim=-1) >= top_p
sorted_logits[sorted_mask] = float('-inf')
# 恢复原始顺序
logits = sorted_logits.scatter(-1, sorted_indices, sorted_logits)
# 采样
probs = F.softmax(logits, dim=-1)
return torch.multinomial(probs, num_samples=1).squeeze(-1)
# 使用示例
batch_size, vocab_size = 4, 50000
logits = torch.randn(batch_size, vocab_size, device='cuda')
# 不同采样策略
greedy_tokens = batch_sample(logits, temperature=1e-9) # Greedy
random_tokens = batch_sample(logits, temperature=1.0) # 随机
top_k_tokens = batch_sample(logits, temperature=0.8, top_k=50) # Top-K
top_p_tokens = batch_sample(logits, temperature=0.7, top_p=0.9) # Nucleus
combined = batch_sample(logits, temperature=0.8, top_k=50, top_p=0.9) # 组合
Gibbs 采样是 MCMC 的一种特殊情况:当直接从联合分布 p(x,y) 采样困难时,轮流从条件分布 p(x|y) 和 p(y|x) 采样。在概率图模型(如 LDA 主题模型)中广泛使用。
import numpy as np
from scipy import stats
def gibbs_bivariate_normal(n_samples=5000, rho=0.8, burn_in=500):
"""
Gibbs 采样:从二元正态分布 N(0, Σ) 采样
Σ = [[1, rho], [rho, 1]]
轮流从条件分布采样:
p(x|y) = N(rho·y, 1-rho²)
p(y|x) = N(rho·x, 1-rho²)
"""
samples = np.zeros((n_samples, 2))
x, y = 0.0, 0.0 # 初始值
var = 1 - rho ** 2
for i in range(n_samples + burn_in):
# 从 p(x|y) 采样
x = np.random.normal(rho * y, np.sqrt(var))
# 从 p(y|x) 采样
y = np.random.normal(rho * x, np.sqrt(var))
if i >= burn_in:
samples[i - burn_in] = [x, y]
return samples
samples = gibbs_bivariate_normal(n_samples=5000, rho=0.8)
print(f"样本均值: ({samples[:, 0].mean():.3f}, {samples[:, 1].mean():.3f})")
print(f"样本相关系数: {np.corrcoef(samples[:, 0], samples[:, 1])[0,1]:.3f}") # ≈ 0.8
print(f"样本方差: ({samples[:, 0].var():.3f}, {samples[:, 1].var():.3f})") # ≈ 1.0
def gibbs_bernoulli_beta(n_samples=5000, a=2, b=5, n_trials=20, burn_in=500):
"""
Beta-Bernoulli 模型的 Gibbs 采样
先验: p ~ Beta(a, b)
似然: x | p ~ Binomial(n, p)
后验条件:
p(p|x) ~ Beta(a + x, b + n - x) (共轭先验)
x|p ~ Binomial(n, p)
"""
samples_p = np.zeros(n_samples)
p = 0.5 # 初始值
x = int(n_trials * p)
for i in range(n_samples + burn_in):
# 从 p(x|p) 采样
x = np.random.binomial(n_trials, p)
# 从 p(p|x) 采样
p = np.random.beta(a + x, b + n_trials - x)
if i >= burn_in:
samples_p[i - burn_in] = p
return samples_p
samples_p = gibbs_bernoulli_beta(n_samples=5000, a=2, b=5, n_trials=20)
print(f"\nBeta-Bernoulli 模型:")
print(f"后验均值: {samples_p.mean():.3f}") # ≈ (a+x)/(a+b+n) ≈ 0.26
print(f"理论均值: {(2+2*0.2)/(2+5+20):.3f}")
深度学习的本质就是优化问题:找到一组参数,使损失函数最小。理解优化的基本概念,是理解训练过程的关键。
想象你被蒙着眼睛放在一片山地上,要找到最低点。你只能用脚感受坡度(梯度)。梯度下降——往最陡的方向走一步。反复走,最终到达某个低谷。但你无法确定这是不是整个山区的最低点(全局最优),还是只是一个小坑(局部最优)。
深度学习的损失函数是高维非凸的。但研究表明:① 大多数局部极小值和全局极小值差不多好;② 鞍点比局部极小值更常见;③ 损失景观有很多"平坦区域",好的解往往在平坦区域中(泛化好)。
import numpy as np
def mse_loss(y_pred, y_true):
"""均方误差:回归任务"""
return np.mean((y_pred - y_true) ** 2)
def cross_entropy_loss(logits, labels):
"""交叉熵:分类任务"""
# Softmax
exp_logits = np.exp(logits - logits.max(axis=1, keepdims=True))
probs = exp_logits / exp_logits.sum(axis=1, keepdims=True)
# 交叉熵
n = len(labels)
log_probs = np.log(probs[range(n), labels] + 1e-9)
return -np.mean(log_probs)
def binary_cross_entropy(y_pred, y_true):
"""二元交叉熵"""
return -np.mean(y_true * np.log(y_pred + 1e-9) +
(1 - y_true) * np.log(1 - y_pred + 1e-9))
def cosine_similarity_loss(a, b):
"""余弦相似度损失:对比学习用"""
cos_sim = np.dot(a, b) / (np.linalg.norm(a) * np.linalg.norm(b) + 1e-9)
return 1 - cos_sim # 越相似,损失越小
import numpy as np
def visualize_gradient_descent():
"""演示不同学习率对梯度下降的影响"""
# 目标函数:f(x) = x²,最小值在 x=0
def f(x): return x ** 2
def grad_f(x): return 2 * x
# 不同学习率
for lr, label in [(0.01, "太小"), (0.1, "合适"), (0.9, "太大")]:
x = 5.0 # 起点
path = [x]
for _ in range(20):
x = x - lr * grad_f(x)
path.append(x)
print(f"lr={lr} ({label}): x 从 5.0 → {x:.4f}, 步数={len(path)-1}")
visualize_gradient_descent()
# lr=0.01 (太小): x 从 5.0 → 0.6773, 步数=20 (太慢)
# lr=0.1 (合适): x 从 5.0 → 0.0000, 步数=20 (收敛)
# lr=0.9 (太大): x 从 5.0 → 0.0000, 步数=20 (震荡但收敛)
一阶优化算法利用梯度(一阶导数)来更新参数。这是深度学习训练的核心——SGD、Momentum、Adam 都是一阶算法。
你蒙着眼在山上找最低点。SGD——每步往最陡的方向走一小步。Momentum——像一个有惯性的球,不仅看当前坡度,还带着之前的势头。Adam——不仅有惯性,还能自动调整步长:陡的地方走小步,平的地方走大步。
每次用一个 mini-batch 计算梯度(近似)。噪声帮助跳出局部最优。
积累历史梯度的指数移动平均。在一致方向上加速,在震荡方向上抑制。
import numpy as np
class Adam:
def __init__(self, lr=0.001, beta1=0.9, beta2=0.999, eps=1e-8):
self.lr = lr
self.beta1 = beta1
self.beta2 = beta2
self.eps = eps
self.m = {} # 一阶矩(均值)
self.v = {} # 二阶矩(方差)
self.t = 0 # 时间步
def update(self, params, grads):
self.t += 1
for key in params:
if key not in self.m:
self.m[key] = np.zeros_like(params[key])
self.v[key] = np.zeros_like(params[key])
# 更新一阶矩和二阶矩
self.m[key] = self.beta1 * self.m[key] + (1 - self.beta1) * grads[key]
self.v[key] = self.beta2 * self.v[key] + (1 - self.beta2) * grads[key]**2
# 偏差修正
m_hat = self.m[key] / (1 - self.beta1**self.t)
v_hat = self.v[key] / (1 - self.beta2**self.t)
# 更新参数
params[key] -= self.lr * m_hat / (np.sqrt(v_hat) + self.eps)
# 使用示例:训练线性回归
X = np.random.randn(200, 3)
y = X @ np.array([1.0, -2.0, 3.0]) + 0.5 + np.random.randn(200) * 0.1
params = {'w': np.zeros(3), 'b': 0.0}
optimizer = Adam(lr=0.01)
for epoch in range(500):
y_pred = X @ params['w'] + params['b']
loss = np.mean((y_pred - y)**2)
grads = {
'w': (2/len(y)) * X.T @ (y_pred - y),
'b': (2/len(y)) * np.sum(y_pred - y)
}
optimizer.update(params, grads)
if epoch % 100 == 0:
print(f"Epoch {epoch}: loss={loss:.4f}")
print(f"学到的权重: {params['w']}") # ≈ [1.0, -2.0, 3.0]
import math
def warmup_cosine_schedule(step, warmup_steps, total_steps, max_lr=1e-3, min_lr=1e-6):
"""Warmup + 余弦衰减学习率调度"""
if step < warmup_steps:
# 线性 warmup
return max_lr * step / warmup_steps
else:
# 余弦衰减
progress = (step - warmup_steps) / (total_steps - warmup_steps)
return min_lr + 0.5 * (max_lr - min_lr) * (1 + math.cos(math.pi * progress))
# 可视化
import matplotlib.pyplot as plt
steps = range(10000)
lrs = [warmup_cosine_schedule(s, 1000, 10000) for s in steps]
plt.plot(steps, lrs)
plt.xlabel('Step'); plt.ylabel('Learning Rate')
plt.title('Warmup + Cosine Decay')
plt.show()
一阶算法只用梯度信息。二阶算法还利用曲率(二阶导数)信息,理论上收敛更快,但计算成本更高。
一阶优化像"看地面走路"——知道哪个方向是下坡。二阶优化像"看地形图走路"——不仅知道方向,还知道坡度在变化(是越来越陡还是越来越平)。后者能更好地规划步长。
收敛速度快(二次收敛),但需要计算和存储 H⁻¹——对 n 个参数就是 n×n 矩阵。深度学习有百万参数,直接用牛顿法不现实。
梯度爆炸是 RNN 和深层网络的常见问题。
大多数深度学习任务不需要二阶优化。Adam/AdamW + 梯度裁剪 + 学习率调度就够了。二阶方法在以下场景有价值:① 大 batch 训练(K-FAC);② 强化学习(自然梯度);③ 小数据精确优化(L-BFGS)。
import numpy as np
def newton_method(f, grad_f, hess_f, x0, tol=1e-8, max_iter=100):
"""牛顿法:用二阶信息找极小值"""
x = x0
for i in range(max_iter):
g = grad_f(x)
H = hess_f(x)
# 检查海森矩阵是否正定
if np.isscalar(H):
dx = -g / H
else:
dx = -np.linalg.solve(H, g) # 解线性方程组 H·dx = -g
x = x + dx
if abs(g) < tol if np.isscalar(g) else np.linalg.norm(g) < tol:
break
return x, i + 1
# 示例:最小化 f(x) = x⁴ - 3x³ + 2
f = lambda x: x**4 - 3*x**3 + 2
grad_f = lambda x: 4*x**3 - 9*x**2
hess_f = lambda x: 12*x**2 - 18*x
x_min, iters = newton_method(f, grad_f, hess_f, x0=0.5)
print(f"极小值点: x = {x_min:.6f}, 迭代次数: {iters}")
print(f"极小值: f(x) = {f(x_min):.6f}")
# 对比梯度下降
def gradient_descent(f, grad_f, x0, lr=0.01, max_iter=10000):
x = x0
for i in range(max_iter):
x = x - lr * grad_f(x)
return x, i + 1
x_gd, iters_gd = gradient_descent(f, grad_f, x0=0.5)
print(f"梯度下降: x = {x_gd:.6f}, 迭代次数: {iters_gd}")
# 牛顿法 ~5 次收敛,梯度下降 ~数千次
import numpy as np
def lbfgs(f, grad_f, x0, m=10, max_iter=100, tol=1e-6):
"""L-BFGS:有限内存拟牛顿法,用最近 m 次梯度变化近似海森矩阵"""
x = x0.copy()
s_list, y_list = [], [] # 存储 x 和梯度的变化
for k in range(max_iter):
g = grad_f(x)
if np.linalg.norm(g) < tol: break
# 两步循环计算近似海森逆 × 梯度
q = g.copy(); alphas = []
for s, y in reversed(list(zip(s_list, y_list))):
rho = 1.0 / (y @ s)
alphas.append(rho * (s @ q))
q -= alphas[-1] * y
alphas.reverse()
if s_list:
s, y = s_list[-1], y_list[-1]
r = (s @ y) / (y @ y) * q
else:
r = q
for i, (s, y) in enumerate(zip(s_list, y_list)):
rho = 1.0 / (y @ s)
beta = rho * (y @ r)
r += s * (alphas[i] - beta)
d = -r
alpha = 1.0
while f(x + alpha * d) > f(x) + 1e-4 * alpha * (g @ d):
alpha *= 0.5 # 回溯线搜索
x_new = x + alpha * d
g_new = grad_f(x_new)
s_list.append(x_new - x); y_list.append(g_new - g)
if len(s_list) > m: s_list.pop(0); y_list.pop(0)
x = x_new
return x, k + 1
f = lambda x: x[0]**2 + 2*x[1]**2
grad_f = lambda x: np.array([2*x[0], 4*x[1]])
x_min, iters = lbfgs(f, grad_f, np.array([3.0, 3.0]))
print(f"L-BFGS 极小值点: {np.round(x_min, 6)}, 迭代: {iters}")
import torch
# PyTorch 原生混合精度训练
scaler = torch.cuda.amp.GradScaler()
for batch in dataloader:
optimizer.zero_grad()
with torch.cuda.amp.autocast(): # 自动 FP16 前向
output = model(batch)
loss = criterion(output, target)
scaler.scale(loss).backward() # 放大 loss 防止 FP16 梯度下溢
scaler.unscale_(optimizer) # 反缩放梯度
torch.nn.utils.clip_grad_norm_(model.parameters(), 1.0)
scaler.step(optimizer)
scaler.update() # 动态调整 scale factor
在同一优化问题上对比不同优化器的收敛行为,直观理解它们的差异。
import numpy as np
def compare_optimizers():
"""
对比不同优化器在 Rosenbrock 函数上的收敛速度
f(x,y) = (1-x)² + 100(y-x²)² ——经典非凸优化测试函数
最小值在 (1,1)
"""
f = lambda x: (1 - x[0])**2 + 100 * (x[1] - x[0]**2)**2
grad = lambda x: np.array([
-2*(1-x[0]) + 200*(x[1]-x[0]**2)*(-2*x[0]),
200*(x[1]-x[0]**2)
])
x0 = np.array([-1.0, 1.0]) # 起点
lr = 0.001
n_steps = 5000
# 1. SGD(无动量)
x = x0.copy()
sgd_losses = []
for _ in range(n_steps):
g = grad(x)
x = x - lr * g
sgd_losses.append(f(x))
# 2. Momentum
x = x0.copy()
v = np.zeros(2)
mom_losses = []
beta = 0.9
for _ in range(n_steps):
g = grad(x)
v = beta * v + g
x = x - lr * v
mom_losses.append(f(x))
# 3. Adam
x = x0.copy()
m = np.zeros(2)
v = np.zeros(2)
adam_losses = []
beta1, beta2, eps = 0.9, 0.999, 1e-8
for t in range(1, n_steps + 1):
g = grad(x)
m = beta1 * m + (1 - beta1) * g
v = beta2 * v + (1 - beta2) * g**2
m_hat = m / (1 - beta1**t)
v_hat = v / (1 - beta2**t)
x = x - lr * m_hat / (np.sqrt(v_hat) + eps)
adam_losses.append(f(x))
# 打印对比结果
for step in [100, 500, 1000, 3000, 4999]:
print(f"Step {step:>5}: SGD={sgd_losses[step]:.4f}, "
f"Momentum={mom_losses[step]:.4f}, Adam={adam_losses[step]:.4f}")
print(f"\n最终 loss (step {n_steps}):")
print(f" SGD: {sgd_losses[-1]:.6f}")
print(f" Momentum: {mom_losses[-1]:.6f}")
print(f" Adam: {adam_losses[-1]:.6f}")
compare_optimizers()
# Adam 收敛最快,Momentum 次之,纯 SGD 最慢
# 但 SGD 的最终解往往泛化更好(更平坦的极小值)
强化学习(RL)是 AI 的第三大范式(继监督学习和无监督学习之后)。核心思想:智能体通过与环境交互,根据奖励信号学习最优策略。
训练一只狗。你不能告诉它每一步该怎么做(没有标签),但它做对了就给零食(奖励),做错了就不给。狗通过反复尝试,学会哪些动作能获得更多零食。这就是强化学习——从奖励中学习行为。
import numpy as np
import gymnasium as gym
class QLearningAgent:
"""Q-Learning 智能体:与 Gymnasium 标准环境交互"""
def __init__(self, n_states, n_actions, lr=0.1, gamma=0.99, epsilon=0.1):
self.q_table = np.zeros((n_states, n_actions))
self.lr = lr
self.gamma = gamma
self.epsilon = epsilon
def choose_action(self, state):
if np.random.random() < self.epsilon:
return np.random.randint(self.q_table.shape[1])
return np.argmax(self.q_table[state])
def update(self, state, action, reward, next_state, done):
if done:
td_target = reward
else:
td_target = reward + self.gamma * np.max(self.q_table[next_state])
self.q_table[state][action] += self.lr * (td_target - self.q_table[state][action])
# 使用 Gymnasium 的 FrozenLake 环境
env = gym.make('FrozenLake-v1', is_slippery=False)
agent = QLearningAgent(env.observation_space.n, env.action_space.n)
for episode in range(10000):
state, _ = env.reset()
done = False
while not done:
action = agent.choose_action(state)
next_state, reward, terminated, truncated, _ = env.step(action)
done = terminated or truncated
agent.update(state, action, reward, next_state, done)
state = next_state
# 评估
successes = 0
for _ in range(1000):
state, _ = env.reset()
done = False
while not done:
action = np.argmax(agent.q_table[state])
state, reward, terminated, truncated, _ = env.step(action)
done = terminated or truncated
successes += reward
print(f"成功率: {successes/1000:.1%}")
import torch
import torch.nn as nn
import gymnasium as gym
class PolicyNetwork(nn.Module):
"""策略网络:输入状态,输出动作概率"""
def __init__(self, state_dim, action_dim):
super().__init__()
self.net = nn.Sequential(
nn.Linear(state_dim, 64), nn.ReLU(),
nn.Linear(64, 64), nn.ReLU(),
nn.Linear(64, action_dim)
)
def forward(self, x):
return torch.softmax(self.net(x), dim=-1)
class ValueNetwork(nn.Module):
"""价值网络:输入状态,输出状态价值"""
def __init__(self, state_dim):
super().__init__()
self.net = nn.Sequential(
nn.Linear(state_dim, 64), nn.ReLU(),
nn.Linear(64, 64), nn.ReLU(),
nn.Linear(64, 1)
)
def forward(self, x):
return self.net(x)
def ppo_update(policy, value_net, optimizer_policy, optimizer_value,
states, actions, old_log_probs, returns, advantages,
clip_epsilon=0.2, epochs=4):
"""PPO 裁剪目标更新"""
for _ in range(epochs):
# 策略网络
probs = policy(states)
dist = torch.distributions.Categorical(probs)
new_log_probs = dist.log_prob(actions)
ratio = torch.exp(new_log_probs - old_log_probs)
surr1 = ratio * advantages
surr2 = torch.clamp(ratio, 1-clip_epsilon, 1+clip_epsilon) * advantages
policy_loss = -torch.min(surr1, surr2).mean()
optimizer_policy.zero_grad()
policy_loss.backward()
optimizer_policy.step()
# 价值网络
value_loss = nn.MSELoss()(value_net(states).squeeze(), returns)
optimizer_value.zero_grad()
value_loss.backward()
optimizer_value.step()
# 训练循环
env = gym.make('CartPole-v1')
policy = PolicyNetwork(4, 2)
value_net = ValueNetwork(4)
opt_p = torch.optim.Adam(policy.parameters(), lr=3e-4)
opt_v = torch.optim.Adam(value_net.parameters(), lr=1e-3)
for episode in range(500):
state, _ = env.reset()
states, actions, rewards, log_probs = [], [], [], []
done = False
while not done:
s = torch.FloatTensor(state).unsqueeze(0)
probs = policy(s)
dist = torch.distributions.Categorical(probs)
action = dist.sample()
next_state, reward, terminated, truncated, _ = env.step(action.item())
done = terminated or truncated
states.append(s); actions.append(action)
rewards.append(reward); log_probs.append(dist.log_prob(action))
state = next_state
# 计算回报和优势
returns = []
G = 0
for r in reversed(rewards):
G = r + 0.99 * G
returns.insert(0, G)
returns = torch.FloatTensor(returns)
states_t = torch.cat(states)
advantages = returns - value_net(states_t).squeeze().detach()
ppo_update(policy, value_net, opt_p, opt_v,
states_t, torch.stack(actions),
torch.stack(log_probs), returns, advantages)
if episode % 50 == 0:
print(f"Episode {episode}: reward={sum(rewards)}")
# PPO 的核心:裁剪目标函数
# L_CLIP = E[min(r(θ)·A, clip(r(θ), 1-ε, 1+ε)·A)]
# 其中 r(θ) = π_new(a|s) / π_old(a|s) 是新旧策略的比值
def ppo_update(policy, optimizer, states, actions, old_log_probs,
advantages, clip_epsilon=0.2):
"""PPO 裁剪目标"""
# 计算新策略的 log 概率
new_log_probs = policy.log_prob(states, actions)
# 概率比
ratio = torch.exp(new_log_probs - old_log_probs)
# 裁剪目标
surr1 = ratio * advantages
surr2 = torch.clamp(ratio, 1 - clip_epsilon, 1 + clip_epsilon) * advantages
policy_loss = -torch.min(surr1, surr2).mean()
# 更新
optimizer.zero_grad()
policy_loss.backward()
optimizer.step()
return policy_loss.item()
# RLHF 训练流程
# 1. 收集人类偏好数据 (prompt, chosen, rejected)
# 2. 训练奖励模型 R(prompt, response) → score
# 3. 用 PPO 优化策略:max E[R(prompt, response)] - β·KL(π || π_ref)
# DPO:直接偏好优化,不需要奖励模型
# L_DPO = -E[log σ(β · (log π(y_w|x)/π_ref(y_w|x) - log π(y_l|x)/π_ref(y_l|x)))]
# y_w = 偏好的回答, y_l = 不偏好的回答
import torch
import torch.nn.functional as F
def dpo_loss(policy_logps, ref_logps, preferred_idx, beta=0.1):
"""
policy_logps: [batch, 2] 模型对两个回答的 log 概率
ref_logps: [batch, 2] 参考模型对两个回答的 log 概率
preferred_idx: [batch] 每个样本中偏好的回答索引(0 或 1)
"""
# 计算 log 比值
log_ratios = policy_logps - ref_logps # [batch, 2]
# 偏好回答的 log 比值 - 非偏好回答的 log 比值
preferred = log_ratios[torch.arange(len(preferred_idx)), preferred_idx]
rejected = log_ratios[torch.arange(len(preferred_idx)), 1 - preferred_idx]
# DPO 损失
loss = -F.logsigmoid(beta * (preferred - rejected)).mean()
return loss
矩阵分解把一个大矩阵拆成几个小矩阵的乘积。它不仅是线性代数的核心工具,更是推荐系统、降维和信号处理的基础。
你有一张巨大的评分表:100 万用户 × 10 万部电影,99% 是空的(用户没看过那些电影)。你想预测空格里的分数。矩阵分解的思路:每个用户的偏好可以用 10 个数字概括(喜欢动作片吗?喜欢喜剧吗?……),每部电影也可以用 10 个数字描述。用户对电影的评分 ≈ 用户向量 · 电影向量的点积。这就是把一个 100 万 × 10 万的大矩阵,分解成 100 万 × 10 和 10 × 10 万两个小矩阵。
任何矩阵 A 都可以分解为:A = UΣV^T
只保留前 k 个最大的奇异值,得到秩为 k 的最佳近似。这就是 PCA 的数学基础。推荐系统中,k 通常取 50-200。
约束所有矩阵元素非负。分解结果具有更好的可解释性——每个分量代表一个"部件"。
import numpy as np
def svd_recommend(ratings, k=2):
"""
简化的 SVD 推荐系统
ratings: 用户×物品评分矩阵(0 表示未评分)
k: 隐因子维度
"""
# 用 numpy 的 SVD
U, sigma, Vt = np.linalg.svd(ratings, full_matrices=False)
# 截断到 k 维
U_k = U[:, :k]
sigma_k = np.diag(sigma[:k])
Vt_k = Vt[:k, :]
# 重构评分矩阵
predicted = U_k @ sigma_k @ Vt_k
return predicted
# 示例:4 个用户 × 5 部电影
ratings = np.array([
[5, 3, 0, 1, 4], # 用户 0
[4, 0, 0, 1, 2], # 用户 1
[0, 1, 2, 4, 0], # 用户 2
[1, 0, 3, 5, 0], # 用户 3
], dtype=float)
predicted = svd_recommend(ratings, k=2)
print("原始评分矩阵:")
print(ratings)
print("\nSVD 预测矩阵(填补了空白):")
print(np.round(predicted, 1))
print(f"\n用户 2 对电影 0 的预测评分: {predicted[2, 0]:.1f}")
Netflix Prize 的实用解法。交替固定 P 和 Q,各自用最小二乘求解。天然支持并行化。
def als_factorization(R, k=10, reg=0.1, epochs=20):
"""ALS:交替固定 P/Q,分别求解。可并行,收敛稳定。"""
n_users, n_items = R.shape
P = np.random.normal(0, 0.1, (n_users, k))
Q = np.random.normal(0, 0.1, (n_items, k))
for epoch in range(epochs):
# 固定 Q,求 P
for i in range(n_users):
rated = np.where(R[i] > 0)[0]
if len(rated) == 0: continue
Q_sub = Q[rated]
P[i] = np.linalg.solve(Q_sub.T @ Q_sub + reg*np.eye(k), Q_sub.T @ R[i, rated])
# 固定 P,求 Q
for j in range(n_items):
rated = np.where(R[:, j] > 0)[0]
if len(rated) == 0: continue
P_sub = P[rated]
Q[j] = np.linalg.solve(P_sub.T @ P_sub + reg*np.eye(k), P_sub.T @ R[rated, j])
rmse = np.sqrt(((R - P @ Q.T)[R > 0] ** 2).mean())
if epoch % 5 == 0: print(f"Epoch {epoch}: RMSE={rmse:.4f}")
return P, Q
隐式反馈场景(点击、浏览)没有明确评分。BPR 通过对比正负样本来学习排序:正样本得分应高于负样本。
class BPR(nn.Module):
"""贝叶斯个性化排序:正样本得分 > 负样本得分"""
def __init__(self, n_users, n_items, k=32):
super().__init__()
self.user_emb = nn.Embedding(n_users, k)
self.item_emb = nn.Embedding(n_items, k)
def forward(self, user, pos_item, neg_item):
u = self.user_emb(user)
pos = self.item_emb(pos_item)
neg = self.item_emb(neg_item)
diff = (u * pos).sum(1) - (u * neg).sum(1)
return -torch.log(torch.sigmoid(diff) + 1e-9).mean()
BPR 的训练关键:负采样——用户交互过的物品是正样本,随机采样未交互的物品作为负样本。训练目标是让正样本得分高于负样本。
import torch
import torch.nn as nn
import numpy as np
class BPR(nn.Module):
"""贝叶斯个性化排序:正样本得分 > 负样本得分"""
def __init__(self, n_users, n_items, k=32):
super().__init__()
self.user_emb = nn.Embedding(n_users, k)
self.item_emb = nn.Embedding(n_items, k)
# 初始化
nn.init.normal_(self.user_emb.weight, std=0.01)
nn.init.normal_(self.item_emb.weight, std=0.01)
def forward(self, user, pos_item, neg_item):
u = self.user_emb(user)
pos = self.item_emb(pos_item)
neg = self.item_emb(neg_item)
diff = (u * pos).sum(1) - (u * neg).sum(1)
return -torch.log(torch.sigmoid(diff) + 1e-9).mean()
def predict(self, user):
"""预测用户对所有物品的得分"""
u = self.user_emb(user) # [1, k]
scores = u @ self.item_emb.weight.T # [1, n_items]
return scores
def build_user_item_dict(interactions):
"""构建用户→交互物品集合"""
user_items = {}
for u, i in interactions:
user_items.setdefault(u, set()).add(i)
return user_items
def negative_sample(user, n_items, pos_items, n_neg=1):
"""负采样:随机选用户未交互过的物品"""
neg_items = []
for _ in range(n_neg):
while True:
neg = np.random.randint(n_items)
if neg not in pos_items:
neg_items.append(neg)
break
return neg_items
def train_bpr(model, interactions, n_items, epochs=50, lr=0.01, batch_size=512):
"""BPR 训练循环"""
optimizer = torch.optim.Adam(model.parameters(), lr=lr, weight_decay=1e-5)
user_items = build_user_item_dict(interactions)
for epoch in range(epochs):
model.train()
np.random.shuffle(interactions)
total_loss = 0
n_batches = 0
for start in range(0, len(interactions), batch_size):
batch = interactions[start:start+batch_size]
users, pos_items, neg_items = [], [], []
for u, pos_i in batch:
neg_i = negative_sample(u, n_items, user_items[u])[0]
users.append(u)
pos_items.append(pos_i)
neg_items.append(neg_i)
users = torch.LongTensor(users)
pos_items = torch.LongTensor(pos_items)
neg_items = torch.LongTensor(neg_items)
loss = model(users, pos_items, neg_items)
optimizer.zero_grad()
loss.backward()
optimizer.step()
total_loss += loss.item()
n_batches += 1
if epoch % 10 == 0:
print(f"Epoch {epoch}: Loss={total_loss/n_batches:.4f}")
return model
def evaluate_bpr(model, test_interactions, user_items_train, k=10):
"""离线评估:Hit@K 和 NDCG@K"""
model.eval()
hits = 0
ndcg = 0
n_users = 0
# 按用户分组测试集
test_by_user = {}
for u, i in test_interactions:
test_by_user.setdefault(u, set()).add(i)
with torch.no_grad():
for u, true_items in test_by_user.items():
scores = model.predict(torch.LongTensor([u]))[0]
# 屏蔽训练集中已交互的物品
if u in user_items_train:
for i in user_items_train[u]:
scores[i] = -float('inf')
# 取 Top-K
_, top_k_indices = torch.topk(scores, k)
top_k_set = set(top_k_indices.numpy())
# Hit@K:测试物品是否在 Top-K 中
hit_items = top_k_set & true_items
if hit_items:
hits += 1
# NDCG@K:第一个命中的排名
for rank, idx in enumerate(top_k_indices.numpy()):
if idx in true_items:
ndcg += 1 / np.log2(rank + 2)
break
n_users += 1
hit_rate = hits / n_users if n_users > 0 else 0
avg_ndcg = ndcg / n_users if n_users > 0 else 0
print(f"Hit@{k}: {hit_rate:.4f}")
print(f"NDCG@{k}: {avg_ndcg:.4f}")
return hit_rate, avg_ndcg
# 完整示例
np.random.seed(42)
torch.manual_seed(42)
n_users, n_items = 100, 50
# 模拟交互数据:每个用户随机交互 5-15 个物品
interactions = []
for u in range(n_users):
n_interact = np.random.randint(5, 15)
items = np.random.choice(n_items, n_interact, replace=False)
for i in items:
interactions.append((u, i))
# 划分训练/测试集
np.random.shuffle(interactions)
split = int(len(interactions) * 0.8)
train_data = interactions[:split]
test_data = interactions[split:]
# 训练
model = BPR(n_users, n_items, k=32)
model = train_bpr(model, train_data, n_items, epochs=50, lr=0.01)
# 评估
user_items_train = build_user_item_dict(train_data)
evaluate_bpr(model, test_data, user_items_train, k=10)
高维数据不仅计算慢,而且有"维度诅咒"——高维空间中距离变得没有意义。降维把高维数据映射到低维,保留最重要的结构信息。
你拍了一张 1000×1000 像素的照片(100 万维)。但照片中的猫只需要几个特征就能描述:颜色、大小、耳朵形状。降维就是从 100 万个像素中提取出这几个关键特征——信息损失最小,但维度从 100 万降到了 10。
词嵌入是 NLP 中最重要的降维——把 one-hot 编码(词表大小维)映射到低维稠密向量。
import numpy as np
def pca(X, n_components=2):
"""PCA:主成分分析"""
# 1. 中心化
mean = X.mean(axis=0)
X_centered = X - mean
# 2. 计算协方差矩阵
cov = np.cov(X_centered.T)
# 3. 特征分解
eigenvalues, eigenvectors = np.linalg.eigh(cov)
# 4. 按特征值降序排列
idx = np.argsort(eigenvalues)[::-1]
eigenvalues = eigenvalues[idx]
eigenvectors = eigenvectors[:, idx]
# 5. 取前 k 个主成分
components = eigenvectors[:, :n_components]
# 6. 投影
X_reduced = X_centered @ components
# 解释方差比
explained_ratio = eigenvalues[:n_components] / eigenvalues.sum()
return X_reduced, explained_ratio
# 示例:4 维数据降到 2 维
np.random.seed(42)
X = np.random.randn(100, 4) @ np.array([[1,0.5],[0.5,1],[0.1,0],[0,0.1]])
X_reduced, ratio = pca(X, n_components=2)
print(f"原始维度: {X.shape[1]}D → 降维后: {X_reduced.shape[1]}D")
print(f"解释方差比: {ratio}") # 大部分信息保留
import numpy as np
class SimpleWord2Vec:
"""简化版 Word2Vec Skip-gram"""
def __init__(self, vocab_size, embedding_dim=50, lr=0.01):
self.W_in = np.random.randn(vocab_size, embedding_dim) * 0.01 # 输入矩阵
self.W_out = np.random.randn(embedding_dim, vocab_size) * 0.01 # 输出矩阵
self.lr = lr
def train_pair(self, center_idx, context_idx):
"""训练一个 (中心词, 上下文词) 对"""
# 前向
h = self.W_in[center_idx] # 隐藏层 = 中心词的嵌入
scores = h @ self.W_out # 输出分数
probs = np.exp(scores - scores.max())
probs = probs / probs.sum()
# 反向传播
probs[context_idx] -= 1 # 梯度
dW_out = np.outer(h, probs)
dh = self.W_out @ probs
dW_in = np.zeros_like(self.W_in)
dW_in[center_idx] = dh
# 更新
self.W_in -= self.lr * dW_in
self.W_out -= self.lr * dW_out
return -np.log(probs[context_idx] + 1e-9) # 损失
def get_embedding(self, word_idx):
return self.W_in[word_idx]
# 词向量的神奇性质
# vec("king") - vec("man") + vec("woman") ≈ vec("queen")
大模型效果好但太大——GPT-3 有 1750 亿参数,占 350GB 内存。模型压缩的目标:在尽量不损失精度的前提下,减小模型体积、加快推理速度。
你写了一本 1000 页的书,但读者只想带一本 100 页的口袋书。模型压缩就是把那 1000 页精华浓缩到 100 页——去掉冗余内容(剪枝),用简写代替全称(量化),让一个学生总结要点(蒸馏)。
用更少的比特表示权重。FP32→FP16→INT8→INT4。
import numpy as np
def quantize_to_int8(float_tensor):
"""对称量化:FP32 → INT8"""
# 找到最大绝对值
abs_max = np.abs(float_tensor).max()
# 计算缩放因子
scale = abs_max / 127.0
# 量化
int8_tensor = np.clip(np.round(float_tensor / scale), -128, 127).astype(np.int8)
return int8_tensor, scale
def dequantize(int8_tensor, scale):
"""反量化:INT8 → FP32"""
return int8_tensor.astype(np.float32) * scale
# 示例
weights = np.random.randn(1000, 1000).astype(np.float32)
print(f"原始大小: {weights.nbytes / 1024:.0f} KB") # 3906 KB
q_weights, scale = quantize_to_int8(weights)
print(f"量化后大小: {q_weights.nbytes / 1024:.0f} KB") # 977 KB (4x 压缩)
# 反量化后检查精度损失
recovered = dequantize(q_weights, scale)
error = np.abs(weights - recovered).mean()
print(f"平均误差: {error:.6f}") # 很小
import torch
import torch.nn as nn
class LoRALinear(nn.Module):
"""LoRA:低秩适应,只训练 A 和 B 两个小矩阵"""
def __init__(self, original_linear, rank=8, alpha=16):
super().__init__()
self.original = original_linear
self.original.weight.requires_grad_(False) # 冻结原始权重
d_out, d_in = original_linear.weight.shape
self.lora_A = nn.Parameter(torch.randn(d_in, rank) * 0.01)
self.lora_B = nn.Parameter(torch.zeros(rank, d_out))
self.scaling = alpha / rank
def forward(self, x):
# 原始输出 + LoRA 增量
original_out = self.original(x)
lora_out = (x @ self.lora_A @ self.lora_B) * self.scaling
return original_out + lora_out
# 参数量对比
# 原始线性层: 4096 × 4096 = 16.7M 参数
# LoRA (rank=8): 4096×8 + 8×4096 = 65K 参数 (256x 减少!)
import torch
import torch.nn as nn
import torch.nn.functional as F
class DistillationLoss(nn.Module):
"""知识蒸馏损失:让学生模仿教师的软标签"""
def __init__(self, temperature=4.0, alpha=0.7):
super().__init__()
self.T = temperature # 温度参数:越大分布越平滑
self.alpha = alpha # 蒸馏损失的权重
def forward(self, student_logits, teacher_logits, labels):
"""
student_logits: 学生模型的输出 logits
teacher_logits: 教师模型的输出 logits
labels: 真实标签
"""
# 1. 软标签损失(KL 散度)
# 用温度 T 平滑 softmax 分布
soft_student = F.log_softmax(student_logits / self.T, dim=-1)
soft_teacher = F.softmax(teacher_logits / self.T, dim=-1)
# KL 散度 × T²(补偿温度缩放对梯度的影响)
soft_loss = F.kl_div(soft_student, soft_teacher, reduction='batchmean') * (self.T ** 2)
# 2. 硬标签损失(标准交叉熵)
hard_loss = F.cross_entropy(student_logits, labels)
# 3. 加权组合
return self.alpha * soft_loss + (1 - self.alpha) * hard_loss
# 示例:3 分类问题
torch.manual_seed(42)
n_classes = 3
batch_size = 8
# 教师模型的输出(更"自信"的分布)
teacher_logits = torch.randn(batch_size, n_classes) * 2
# 学生模型的输出(还在学习中)
student_logits = torch.randn(batch_size, n_classes)
labels = torch.randint(0, n_classes, (batch_size,))
# 计算蒸馏损失
criterion = DistillationLoss(temperature=4.0, alpha=0.7)
loss = criterion(student_logits, teacher_logits, labels)
print(f"蒸馏损失: {loss.item():.4f}")
# 对比:不同温度的效果
for T in [1, 2, 4, 8, 16]:
soft_teacher = F.softmax(teacher_logits / T, dim=-1)
entropy = -(soft_teacher * soft_teacher.log()).sum(-1).mean()
print(f"T={T:>2}: 熵={entropy:.3f}, 分布=[{soft_teacher[0].detach().numpy().round(3)}]")
# T 越大,分布越平滑,学生能学到更多"暗知识"(类间关系)
大模型训练一次,推理无数次。推理效率直接影响用户体验和运营成本。本章介绍让 LLM 推理更快的核心算法。
你在写一篇文章。普通推理——每写一个字,都要从头回顾全文。KV Cache——把之前算好的"笔记"存起来,写新字时只看笔记,不用重读全文。FlashAttention——用更高效的方式整理笔记,减少翻页次数。
Transformer 自回归生成时,每个 token 都要和前面所有 token 计算注意力。KV Cache 缓存已计算的 Key 和 Value,避免重复计算。
标准注意力的瓶颈不是计算量,而是内存访问(HBM 读写)。FlashAttention 通过分块计算,减少内存访问。
# 标准注意力的内存问题
# Q, K, V: [batch, heads, seq_len, d_model]
# 注意力矩阵 A = Q @ K^T: [batch, heads, seq_len, seq_len]
# 当 seq_len = 8192 时,A 占用 8192² × 2 bytes = 128 MB(每个头!)
# 这个矩阵必须写入 HBM(高带宽内存),然后再读回来计算 softmax
# FlashAttention 的解决方案:分块计算
def flash_attention_concept(Q, K, V, block_size=256):
"""FlashAttention 的概念实现(实际用 CUDA 实现)"""
N = Q.shape[0]
O = np.zeros_like(Q) # 输出
l = np.zeros(N) # softmax 分母
m = np.full(N, -np.inf) # 当前最大值
# 把 K, V 分成块
for j in range(0, N, block_size):
Kj = K[j:j+block_size] # 从 HBM 加载一块 K
Vj = V[j:j+block_size] # 从 HBM 加载一块 V
for i in range(0, N, block_size):
Qi = Q[i:i+block_size] # 从 HBM 加载一块 Q
# 在 SRAM 中计算注意力(快!)
S_ij = Qi @ Kj.T / np.sqrt(Q.shape[-1])
# 在线 softmax 更新
m_new = np.maximum(m[i:i+block_size], S_ij.max(axis=-1))
exp_S = np.exp(S_ij - m_new[:, None])
l_new = np.exp(m[i:i+block_size] - m_new) * l[i:i+block_size] + exp_S.sum(axis=-1)
O[i:i+block_size] = (
np.exp(m[i:i+block_size] - m_new)[:, None] * l[i:i+block_size][:, None] * O[i:i+block_size]
+ exp_S @ Vj
) / l_new[:, None]
m[i:i+block_size] = m_new
l[i:i+block_size] = l_new
return O
# 关键:O 和 l 在 SRAM 中不断更新,不需要把完整的 N×N 注意力矩阵写入 HBM
class KVCache:
"""KV Cache:缓存已计算的 Key 和 Value"""
def __init__(self):
self.key_cache = None
self.value_cache = None
def update(self, new_key, new_value):
"""拼接新的 KV 到缓存"""
if self.key_cache is None:
self.key_cache = new_key
self.value_cache = new_value
else:
self.key_cache = concat([self.key_cache, new_key], dim=seq_dim)
self.value_cache = concat([self.value_cache, new_value], dim=seq_dim)
return self.key_cache, self.value_cache
def get_seq_len(self):
return self.key_cache.shape[1] if self.key_cache is not None else 0
# 自回归生成流程
def generate_with_kv_cache(model, prompt_tokens, max_new_tokens):
tokens = prompt_tokens
kv_cache = KVCache()
# Prefill:一次性处理所有 prompt tokens
logits, kv_cache = model.forward(tokens, kv_cache)
# Decode:逐个生成新 token
for _ in range(max_new_tokens):
next_token = sample(logits[:, -1, :]) # 只取最后一个位置
tokens = next_token
# 只输入新 token,用缓存的 KV
logits, kv_cache = model.forward(tokens, kv_cache)
if next_token == EOS_TOKEN:
break
return tokens
# 没有 KV Cache:每步都要重新计算所有 token 的 KV → O(n²)
# 有 KV Cache:每步只计算新 token 的 KV → O(n)
# vLLM:工业级高并发推理引擎
# 核心技术:PagedAttention + 连续批处理 + 投机解码
from vllm import LLM, SamplingParams
# 加载模型(自动启用所有优化)
llm = LLM(model="meta-llama/Llama-3-8B-Instruct",
gpu_memory_utilization=0.9,
max_model_len=8192)
# 批量推理
prompts = ["解释 Transformer", "写快速排序", "什么是 RAG", "比较 LoRA 和全量微调"]
params = SamplingParams(temperature=0.7, top_p=0.9, max_tokens=512)
outputs = llm.generate(prompts, params)
# 启动 API 服务:vllm serve model --port 8000
# 然后用 OpenAI 客户端调用
# GGUF / llama.cpp:CPU 边缘部署
# 转换:python convert_hf_to_gguf.py model/ --outtype f16
# 量化:llama-quantize model.gguf model-q4.gguf Q4_K_M
# 运行:llama-cli -m model-q4.gguf -p "你好" -n 128
from llama_cpp import Llama
llm = Llama(model_path="model-q4_k_m.gguf", n_ctx=4096, n_gpu_layers=0)
output = llm("什么是注意力机制", max_tokens=256)
print(output['choices'][0]['text'])
当模型大到一块 GPU 放不下,或者数据多到一块 GPU 训练太慢,就需要分布式训练——用多块 GPU 协同训练。
你要搬 1000 箱货物。数据并行——10 个人每人搬 100 箱,搬完汇总。模型并行——一个大箱子太重,10 个人一起抬。流水线并行——传送带,第 1 个人搬出仓库,第 2 个人装车,第 3 个人运输。
实际训练大模型通常组合使用多种并行策略。
3D 并行 = 数据并行 × 张量并行 × 流水线并行。1000+ 块 GPU,同时在三个维度上并行。
import numpy as np
def allreduce_simulate(gradients, n_workers):
"""
模拟 AllReduce 操作
每个 worker 有自己的梯度,AllReduce 后所有 worker 得到平均梯度
"""
# 模拟:每个 worker 有略微不同的梯度(因为不同的 mini-batch)
worker_grads = []
for i in range(n_workers):
noise = np.random.randn(*gradients.shape) * 0.1
worker_grads.append(gradients + noise)
# AllReduce:所有 worker 交换梯度并取平均
avg_gradient = np.mean(worker_grads, axis=0)
# 每个 worker 都用相同的平均梯度更新
for i in range(n_workers):
assert np.allclose(worker_grads[i], worker_grads[i]) # 保持各自梯度
# AllReduce 后,所有 worker 的梯度都变成 avg_gradient
return avg_gradient
# 梯度累积模拟
def gradient_accumulate(model, dataloader, accumulate_steps=4):
"""
梯度累积:跑 N 步再更新一次
等效于 N 倍的 batch size,但只用 1/N 的显存
"""
accumulated_grads = None
for step, batch in enumerate(dataloader):
# 前向 + 反向(但不更新)
loss = model.forward(batch)
grads = model.backward(loss)
# 累积梯度
if accumulated_grads is None:
accumulated_grads = grads
else:
for key in accumulated_grads:
accumulated_grads[key] += grads[key]
# 每 N 步更新一次
if (step + 1) % accumulate_steps == 0:
for key in accumulated_grads:
accumulated_grads[key] /= accumulate_steps # 取平均
model.update(accumulated_grads)
accumulated_grads = None # 重置
GPU 间通信的核心算法。每块 GPU 只和左右两个邻居通信,通信量与 GPU 数量无关。
| 级别 | 分片内容 | 显存节省 | 通信量 |
|---|---|---|---|
| ZeRO-1 | 优化器状态(如 Adam 的 m, v) | 4x | 与 DDP 相同 |
| ZeRO-2 | 优化器状态 + 梯度 | 8x | 与 DDP 相同 |
| ZeRO-3 | 优化器状态 + 梯度 + 模型参数 | Nx(N=GPU数) | 增加 1.5x |
Adam 优化器对每个参数维护 3 个状态:参数本身(fp32) + 一阶矩 m(fp32) + 二阶矩 v(fp32)。一个 7B 模型需要 7B×12 = 84GB 显存。ZeRO-1 把优化器状态分到 8 块 GPU 上,每块只需 ~10.5GB。
# 混合精度训练的核心:FP16 前向/反向 + FP32 主权重 + Loss Scaling
class MixedPrecisionTrainer:
def __init__(self, model, lr=1e-3, loss_scale=1024):
self.model = model
self.optimizer = torch.optim.Adam(model.parameters(), lr=lr)
self.loss_scale = loss_scale
# FP32 主权重副本
self.master_weights = [p.data.float().clone() for p in model.parameters()]
def train_step(self, x, y):
# 1. 前向(FP16)
with torch.cuda.amp.autocast():
output = self.model(x)
loss = F.cross_entropy(output, y)
# 2. Loss Scaling(防止 FP16 梯度下溢)
scaled_loss = loss * self.loss_scale
# 3. 反向
self.optimizer.zero_grad()
scaled_loss.backward()
# 4. 反缩放梯度 + 裁剪
for p in self.model.parameters():
if p.grad is not None:
p.grad.data /= self.loss_scale
# 5. 更新 FP32 主权重
self.optimizer.step()
# 6. 把 FP32 权重拷回 FP16 模型
for p, master in zip(self.model.parameters(), self.master_weights):
master.copy_(p.data)
p.data = master.half()
NVIDIA Collective Communications Library (NCCL) 是多 GPU 通信的基石。理解这些原语是理解大模型并行的前提。
# PyTorch 分布式通信示例
import torch.distributed as dist
# 初始化进程组(NCCL 后端用于 GPU)
dist.init_process_group(backend='nccl', world_size=4, rank=local_rank)
# All-Reduce:所有 GPU 的梯度求平均
tensor = torch.randn(10, device='cuda')
dist.all_reduce(tensor, op=dist.ReduceOp.AVG)
# 操作后,每块 GPU 上的 tensor 都是所有 GPU tensor 的平均值
# Broadcast:把 rank 0 的参数广播给所有 GPU
dist.broadcast(tensor, src=0)
# All-Gather:收集所有 GPU 的数据
gather_list = [torch.zeros(10, device='cuda') for _ in range(4)]
dist.all_gather(gather_list, tensor)
# Reduce-Scatter:归约后分散
output = torch.zeros(10, device='cuda')
dist.reduce_scatter(output, [tensor]*4, op=dist.ReduceOp.SUM)
# Ring AllReduce 通信量分析
# 数据量 M, GPU 数 N
# Reduce-Scatter: M × (N-1)/N 通信
# All-Gather: M × (N-1)/N 通信
# 总通信量: 2M × (N-1)/N ≈ 2M(与 N 无关!)
数据是 AI 的燃料,但很多数据涉及隐私——医疗记录、金融数据、个人聊天记录。联邦学习让模型去数据那里训练,而不是把数据集中起来。
10 家医院想合作训练一个疾病诊断模型,但每家医院的数据都不能外泄。联邦学习的方案:① 总部发一个模型给各家医院;② 每家用自己的数据训练;③ 只把模型更新(不是数据)发回总部;④ 总部汇总更新,改进模型。数据从未离开医院。
Non-IID 数据——不同客户端的数据分布不同,模型难以收敛。通信成本——梯度传输是瓶颈。公平性——数据多的客户端影响更大。这些是当前研究热点。
import numpy as np
class FedAvgClient:
"""联邦学习客户端"""
def __init__(self, data, labels, lr=0.01):
self.data = data
self.labels = labels
self.lr = lr
self.w = None
def set_weights(self, w):
self.w = w.copy()
def local_train(self, epochs=5):
"""本地训练若干轮"""
for _ in range(epochs):
# 简化的梯度下降
preds = self.data @ self.w
grad = self.data.T @ (preds - self.labels) / len(self.labels)
self.w -= self.lr * grad
return self.w
class FedAvgServer:
"""联邦学习服务端"""
def __init__(self, clients, global_w):
self.clients = clients
self.global_w = global_w
def federated_round(self, n_selected=3, local_epochs=5):
"""一轮联邦训练"""
# 1. 随机选择客户端
selected = np.random.choice(self.clients, n_selected, replace=False)
# 2. 下发全局模型
for client in selected:
client.set_weights(self.global_w)
# 3. 本地训练
local_weights = []
local_sizes = []
for client in selected:
w = client.local_train(epochs=local_epochs)
local_weights.append(w)
local_sizes.append(len(client.data))
# 4. 加权平均(FedAvg)
total_size = sum(local_sizes)
self.global_w = sum(
w * (size / total_size)
for w, size in zip(local_weights, local_sizes)
)
return self.global_w
# 模拟
np.random.seed(42)
true_w = np.array([1.0, -2.0, 3.0])
# 创建 5 个客户端,每个有不同的数据
clients = []
for i in range(5):
X = np.random.randn(50, 3)
y = X @ true_w + np.random.randn(50) * 0.1
clients.append(FedAvgClient(X, y))
# 初始化全局模型
global_w = np.zeros(3)
server = FedAvgServer(clients, global_w)
# 联邦训练 20 轮
for round_num in range(20):
server.federated_round(n_selected=3, local_epochs=5)
print(f"真实权重: {true_w}")
print(f"学到权重: {np.round(server.global_w, 2)}")
import numpy as np
def dp_sgd(gradients, clip_norm=1.0, noise_multiplier=1.1):
"""
差分隐私 SGD:裁剪梯度 + 添加噪声
保证单个样本的存在不会显著影响模型
"""
# 1. 梯度裁剪:限制每个样本梯度的范数
grad_norm = np.linalg.norm(gradients)
if grad_norm > clip_norm:
gradients = gradients * (clip_norm / grad_norm)
# 2. 添加高斯噪声
noise = np.random.normal(0, noise_multiplier * clip_norm, gradients.shape)
noisy_grad = gradients + noise
return noisy_grad
# ε(隐私预算)越小,隐私越好,但精度越差
# 实际中 ε < 10 被认为是合理的隐私保护
学算法最好的方式是动手写代码。本章用 Python 实现本书涉及的核心算法,每个实现都简洁可运行。
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
# 测试
print(binary_search([1,3,5,7,9,11], 7)) # 3
def quicksort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
mid = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quicksort(left) + mid + quicksort(right)
print(quicksort([3,6,8,10,1,2,1])) # [1,1,2,3,6,8,10]
class SimpleHashMap:
def __init__(self, size=1000):
self.size = size
self.buckets = [[] for _ in range(size)]
def _hash(self, key):
return hash(key) % self.size
def put(self, key, value):
idx = self._hash(key)
bucket = self.buckets[idx]
for i, (k, v) in enumerate(bucket):
if k == key:
bucket[i] = (key, value)
return
bucket.append((key, value))
def get(self, key):
idx = self._hash(key)
for k, v in self.buckets[idx]:
if k == key:
return v
raise KeyError(key)
import heapq
class PriorityQueue:
def __init__(self):
self._heap = []
def push(self, item, priority):
heapq.heappush(self._heap, (priority, item))
def pop(self):
return heapq.heappop(self._heap)[1]
def peek(self):
return self._heap[0][1]
def __len__(self):
return len(self._heap)
from collections import deque
def bfs(graph, start):
visited = {start}
queue = deque([start])
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return order
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
order = [start]
for neighbor in graph[start]:
if neighbor not in visited:
order.extend(dfs(graph, neighbor, visited))
return order
import heapq
def dijkstra(graph, start):
dist = {node: float('inf') for node in graph}
dist[start] = 0
heap = [(0, start)]
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]:
continue
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
heapq.heappush(heap, (dist[v], v))
return dist
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # 路径压缩
return self.parent[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py:
return False
if self.rank[px] < self.rank[py]:
px, py = py, px
self.parent[py] = px
if self.rank[px] == self.rank[py]:
self.rank[px] += 1
return True
def lcs(s1, s2):
m, n = len(s1), len(s2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i-1] == s2[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[m][n]
print(lcs("abcde", "ace")) # 3
import numpy as np
def kmeans(X, k, max_iters=100):
n, d = X.shape
# 随机选 k 个初始中心
centroids = X[np.random.choice(n, k, replace=False)]
for _ in range(max_iters):
# 分配:每个点找最近的中心
dists = np.linalg.norm(X[:, None] - centroids, axis=2)
labels = np.argmin(dists, axis=1)
# 更新:重新计算中心
new_centroids = np.array([X[labels == i].mean(axis=0) for i in range(k)])
if np.allclose(centroids, new_centroids):
break
centroids = new_centroids
return labels, centroids
import numpy as np
def gradient_descent(X, y, lr=0.01, epochs=1000):
n, d = X.shape
w = np.zeros(d)
b = 0
for _ in range(epochs):
y_pred = X @ w + b
loss = np.mean((y_pred - y) ** 2)
# 梯度
dw = (2/n) * X.T @ (y_pred - y)
db = (2/n) * np.sum(y_pred - y)
# 更新
w -= lr * dw
b -= lr * db
return w, b
# 线性回归示例
X = np.random.randn(100, 3)
y = X @ np.array([1.0, -2.0, 3.0]) + 0.5
w, b = gradient_descent(X, y)
print(f"学到的权重: {w}, 偏置: {b:.2f}")
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end = True
def search(self, word):
node = self.root
for char in word:
if char not in node.children:
return False
node = node.children[char]
return node.is_end
def starts_with(self, prefix):
node = self.root
for char in prefix:
if char not in node.children:
return False
node = node.children[char]
return True
trie = Trie()
for word in ["apple", "app", "banana", "band"]:
trie.insert(word)
print(trie.search("app")) # True
print(trie.starts_with("ban")) # True
import numpy as np
from collections import Counter
def knn(X_train, y_train, X_test, k=3):
"""简单 KNN 实现"""
predictions = []
for x in X_test:
# 计算到所有训练样本的距离
distances = np.linalg.norm(X_train - x, axis=1)
# 找最近的 k 个
nearest_idx = np.argsort(distances)[:k]
nearest_labels = y_train[nearest_idx]
# 投票
most_common = Counter(nearest_labels).most_common(1)[0][0]
predictions.append(most_common)
return np.array(predictions)
# 示例
X_train = np.array([[1,2],[2,3],[3,4],[6,7],[7,8]])
y_train = np.array([0, 0, 0, 1, 1])
X_test = np.array([[2,2],[5,5]])
print(knn(X_train, y_train, X_test, k=3)) # [0, 1]
import numpy as np
class NaiveBayes:
def fit(self, X, y):
self.classes = np.unique(y)
self.params = {}
for c in self.classes:
X_c = X[y == c]
self.params[c] = {
'mean': X_c.mean(axis=0),
'var': X_c.var(axis=0) + 1e-9, # 防止除零
'prior': len(X_c) / len(X)
}
def _gaussian_likelihood(self, x, mean, var):
return np.exp(-0.5 * ((x - mean)**2 / var)) / np.sqrt(2 * np.pi * var)
def predict(self, X):
predictions = []
for x in X:
posteriors = {}
for c in self.classes:
p = self.params[c]
likelihood = np.prod(self._gaussian_likelihood(x, p['mean'], p['var']))
posteriors[c] = likelihood * p['prior']
predictions.append(max(posteriors, key=posteriors.get))
return np.array(predictions)
import numpy as np
class SimpleNN:
"""两层神经网络:输入→隐藏→输出"""
def __init__(self, input_size, hidden_size, output_size, lr=0.01):
self.W1 = np.random.randn(input_size, hidden_size) * 0.01
self.b1 = np.zeros(hidden_size)
self.W2 = np.random.randn(hidden_size, output_size) * 0.01
self.b2 = np.zeros(output_size)
self.lr = lr
def relu(self, x):
return np.maximum(0, x)
def softmax(self, x):
exp_x = np.exp(x - x.max(axis=1, keepdims=True))
return exp_x / exp_x.sum(axis=1, keepdims=True)
def forward(self, X):
self.z1 = X @ self.W1 + self.b1
self.a1 = self.relu(self.z1)
self.z2 = self.a1 @ self.W2 + self.b2
return self.softmax(self.z2)
def train(self, X, y, epochs=1000):
for epoch in range(epochs):
# 前向
probs = self.forward(X)
# 交叉熵损失
loss = -np.mean(np.log(probs[range(len(y)), y] + 1e-9))
# 反向传播
m = len(y)
dz2 = probs.copy()
dz2[range(m), y] -= 1
dW2 = self.a1.T @ dz2 / m
db2 = dz2.sum(axis=0) / m
da1 = dz2 @ self.W2.T
dz1 = da1 * (self.z1 > 0)
dW1 = X.T @ dz1 / m
db1 = dz1.sum(axis=0) / m
# 更新
self.W2 -= self.lr * dW2
self.b2 -= self.lr * db2
self.W1 -= self.lr * dW1
self.b1 -= self.lr * db1
if epoch % 200 == 0:
print(f"Epoch {epoch}: loss={loss:.4f}")
# 异或问题
X = np.array([[0,0],[0,1],[1,0],[1,1]])
y = np.array([0, 1, 1, 0])
nn = SimpleNN(2, 8, 2, lr=0.5)
nn.train(X, y)
print("预测:", nn.forward(X).argmax(axis=1)) # [0, 1, 1, 0]
以上只是冰山一角。建议:① 把每个算法跑一遍,理解每行代码;② 修改参数看效果变化;③ 在 LeetCode 上刷对应题目;④ 用 PyTorch 实现对应的深度学习版本。算法不是背的,是写出来的。
恭喜你读完了这本 AI 必备算法教程!记住:算法不是目的,解决问题才是目的。不需要记住每个算法的细节——你需要知道有这个工具,以及它能解决什么问题。真正需要的时候,再来查、再来写。这就是工程师的思维方式。
刷题是检验算法理解的最好方式。这 100 道题覆盖了本书所有核心算法,按专题分类,标注了难度和对应章节。建议先读懂本书对应章节,再来刷题。
① 每道题先自己想 15 分钟,想不出来再看提示;② 写完代码要跑通所有测试用例;③ 做完后看 LeetCode 题解区的最优解,对比差距;④ 隔一周再做一遍,确保真正掌握。刷题不在多,在于每题都吃透。
| # | 题目 | 难度 | 核心算法 |
|---|---|---|---|
| 1 | 两数之和 | 🟢 简单 | 哈希表 |
| 15 | 三数之和 | 🟡 中等 | 排序 + 双指针 |
| 11 | 盛最多水的容器 | 🟡 中等 | 双指针 |
| 26 | 删除有序数组中的重复项 | 🟢 简单 | 快慢指针 |
| 27 | 移除元素 | 🟢 简单 | 快慢指针 |
| 283 | 移动零 | 🟢 简单 | 快慢指针 |
| 88 | 合并两个有序数组 | 🟢 简单 | 双指针从后往前 |
| 75 | 颜色分类 | 🟡 中等 | 三指针(荷兰国旗) |
题目:给定数组 nums 和目标值 target,找出和为 target 的两个数的下标。
思路:用哈希表存已遍历的数。对每个 num,检查 target-num 是否在哈希表中。
def twoSum(nums, target):
seen = {}
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
# 时间 O(n),空间 O(n)
题目:找出数组中所有和为 0 的三元组(不重复)。
思路:排序后固定第一个数,对后面部分用双指针找两数之和 = -第一个数。跳过重复元素。
def threeSum(nums):
nums.sort()
result = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i-1]: continue # 跳过重复
lo, hi = i + 1, len(nums) - 1
while lo < hi:
s = nums[i] + nums[lo] + nums[hi]
if s < 0: lo += 1
elif s > 0: hi -= 1
else:
result.append([nums[i], nums[lo], nums[hi]])
while lo < hi and nums[lo] == nums[lo+1]: lo += 1
while lo < hi and nums[hi] == nums[hi-1]: hi -= 1
lo += 1; hi -= 1
return result
# 时间 O(n²),空间 O(1)
题目:给定 n 条垂直线段,找两条线和 x 轴围成的最大面积。
思路:双指针从两端向中间移动。每次移动较短的那条线——因为移动较长的不可能增大面积。
def maxArea(height):
lo, hi = 0, len(height) - 1
max_area = 0
while lo < hi:
area = min(height[lo], height[hi]) * (hi - lo)
max_area = max(max_area, area)
if height[lo] < height[hi]:
lo += 1
else:
hi -= 1
return max_area
# 时间 O(n),空间 O(1)
题目:原地删除有序数组中的重复元素,返回新长度。
思路:快慢指针。慢指针指向已去重部分的末尾,快指针扫描。遇到不同的数就填到慢指针+1 的位置。
def removeDuplicates(nums):
if not nums: return 0
slow = 0
for fast in range(1, len(nums)):
if nums[fast] != nums[slow]:
slow += 1
nums[slow] = nums[fast]
return slow + 1
# 时间 O(n),空间 O(1)
题目:原地移除数组中所有值为 val 的元素,返回新长度。
思路:快慢指针。快指针扫描,遇到非 val 的数就填到慢指针位置。
def removeElement(nums, val):
slow = 0
for fast in range(len(nums)):
if nums[fast] != val:
nums[slow] = nums[fast]
slow += 1
return slow
# 时间 O(n),空间 O(1)
题目:将所有 0 移到数组末尾,保持非零元素相对顺序。
思路:快慢指针。慢指针指向下一个非零元素应填的位置,快指针扫描非零元素填入。
def moveZeroes(nums):
slow = 0
for fast in range(len(nums)):
if nums[fast] != 0:
nums[slow], nums[fast] = nums[fast], nums[slow]
slow += 1
# 时间 O(n),空间 O(1)
题目:将 nums2 合并到 nums1 中(nums1 末尾有足够空间)。
思路:双指针从后往前填充。从最大的数开始比较,避免覆盖未处理的元素。
def merge(nums1, m, nums2, n):
p1, p2, p = m - 1, n - 1, m + n - 1
while p1 >= 0 and p2 >= 0:
if nums1[p1] > nums2[p2]:
nums1[p] = nums1[p1]; p1 -= 1
else:
nums1[p] = nums2[p2]; p2 -= 1
p -= 1
nums1[:p2+1] = nums2[:p2+1] # 剩余的 nums2
# 时间 O(m+n),空间 O(1)
题目:只有 0、1、2 三种数,原地排序。
思路:三指针:lo 指向 0 的右边界,hi 指向 2 的左边界,mid 扫描。0 交换到前面,2 交换到后面。
def sortColors(nums):
lo, mid, hi = 0, 0, len(nums) - 1
while mid <= hi:
if nums[mid] == 0:
nums[lo], nums[mid] = nums[mid], nums[lo]
lo += 1; mid += 1
elif nums[mid] == 1:
mid += 1
else:
nums[mid], nums[hi] = nums[hi], nums[mid]
hi -= 1
# 时间 O(n),空间 O(1)
| # | 题目 | 难度 | 核心算法 |
|---|---|---|---|
| 49 | 字母异位词分组 | 🟡 中等 | 排序后哈希 |
| 128 | 最长连续序列 | 🟡 中等 | 哈希集合 |
| 242 | 有效的字母异位词 | 🟢 简单 | 计数哈希 |
| 383 | 赎金信 | 🟢 简单 | 计数哈希 |
| 202 | 快乐数 | 🟢 简单 | 哈希集合检测循环 |
| 205 | 同构字符串 | 🟢 简单 | 双向哈希映射 |
题目:将字母异位词(字母相同顺序不同)分组。如 ["eat","tea","ate"] 一组。
思路:排序后的字符串作为 key,相同的 key 归为一组。
def groupAnagrams(strs):
from collections import defaultdict
groups = defaultdict(list)
for s in strs:
key = ''.join(sorted(s)) # 排序后作为 key
groups[key].append(s)
return list(groups.values())
# 时间 O(n·k·logk),k 是字符串平均长度
题目:未排序数组,找最长连续序列的长度。如 [100,4,200,1,3,2] → 4(1,2,3,4)。
思路:用 set 存所有数。只从序列的起点开始计数(即 num-1 不在 set 中的数)。
def longestConsecutive(nums):
num_set = set(nums)
max_len = 0
for num in num_set:
if num - 1 not in num_set: # 只从起点开始
length = 1
while num + length in num_set:
length += 1
max_len = max(max_len, length)
return max_len
# 时间 O(n),空间 O(n)
题目:判断两个字符串是否互为字母异位词。
思路:用长度 26 的计数数组。s 中字符 +1,t 中字符 -1。最终全为 0 则是异位词。
def isAnagram(s, t):
if len(s) != len(t): return False
count = [0] * 26
for c in s: count[ord(c) - ord('a')] += 1
for c in t: count[ord(c) - ord('a')] -= 1
return all(c == 0 for c in count)
# 时间 O(n),空间 O(1)
题目:判断 ransomNote 能否由 magazine 中的字符构成(每个字符只能用一次)。
思路:计数 magazine 的字符数,然后消耗 ransomNote 的字符数。
def canConstruct(ransomNote, magazine):
from collections import Counter
mag_count = Counter(magazine)
for c in ransomNote:
if mag_count[c] <= 0:
return False
mag_count[c] -= 1
return True
# 时间 O(n),空间 O(1)
题目:对一个数,不断替换为各位数字的平方和。如果最终变为 1 则是快乐数;如果陷入循环则不是。
思路:用 set 记录出现过的数。如果某个数重复出现,说明进入循环。
def isHappy(n):
seen = set()
while n != 1:
if n in seen: return False
seen.add(n)
n = sum(int(d) ** 2 for d in str(n))
return True
# 时间 O(log n),空间 O(log n)
题目:判断 s 和 t 是否同构(字符映射关系一致)。如 "egg" 和 "add" 同构。
思路:双向映射。s→t 和 t→s 两个方向都要一致。
def isIsomorphic(s, t):
s_to_t, t_to_s = {}, {}
for c1, c2 in zip(s, t):
if (c1 in s_to_t and s_to_t[c1] != c2) or \
(c2 in t_to_s and t_to_s[c2] != c1):
return False
s_to_t[c1] = c2
t_to_s[c2] = c1
return True
# 时间 O(n),空间 O(1)(字符集有限)
| # | 题目 | 难度 | 核心算法 |
|---|---|---|---|
| 206 | 反转链表 | 🟢 简单 | 迭代/递归 |
| 21 | 合并两个有序链表 | 🟢 简单 | 双指针 |
| 141 | 环形链表 | 🟢 简单 | 快慢指针(Floyd) |
| 142 | 环形链表 II | 🟡 中等 | 快慢指针找入口 |
| 19 | 删除链表的倒数第 N 个结点 | 🟡 中等 | 快慢指针间隔 N |
| 160 | 相交链表 | 🟢 简单 | 双指针走对方的路 |
| 25 | K 个一组翻转链表 | 🔴 困难 | 分组反转 |
| 146 | LRU 缓存 | 🟡 中等 | 哈希表 + 双向链表 |
题目:反转一个单链表。如 1→2→3 变成 3→2→1。
思路:迭代法:用 prev/curr/next 三个指针,逐个翻转指向。
def reverseList(head):
prev, curr = None, head
while curr:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
return prev
# 时间 O(n),空间 O(1)
题目:将两个升序链表合并为一个新的升序链表。
思路:双指针逐个比较,小的接到结果链表后面。用哨兵节点简化头节点处理。
def mergeTwoLists(l1, l2):
dummy = ListNode(0)
curr = dummy
while l1 and l2:
if l1.val <= l2.val:
curr.next = l1; l1 = l1.next
else:
curr.next = l2; l2 = l2.next
curr = curr.next
curr.next = l1 or l2
return dummy.next
# 时间 O(m+n),空间 O(1)
题目:判断链表是否有环。
思路:Floyd 龟兔赛跑。快指针走两步,慢指针走一步。如果有环,快指针一定会追上慢指针。
def hasCycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
# 时间 O(n),空间 O(1)
题目:如果有环,返回环的入口节点。
思路:快慢指针相遇后,把一个指针移到头部,两个指针各走一步,再次相遇点即为入口。数学证明:a = c(a 是头到入口,c 是环中相遇点到入口)。
def detectCycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast: # 相遇
ptr = head
while ptr != slow:
ptr = ptr.next
slow = slow.next
return ptr # 入口
return None
# 时间 O(n),空间 O(1)
题目:删除链表倒数第 N 个节点(一趟扫描完成)。
思路:快指针先走 N 步,然后快慢一起走。快到末尾时,慢指针指向待删节点的前一个。
def removeNthFromEnd(head, n):
dummy = ListNode(0, head)
fast = slow = dummy
for _ in range(n + 1):
fast = fast.next
while fast:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return dummy.next
# 时间 O(L),空间 O(1)
题目:找到两个链表的相交节点。
思路:两个指针分别从两个头出发,走到末尾后跳到另一个链表的头部。如果相交,一定在交点相遇(都走了 a+b-c 步)。
def getIntersectionNode(headA, headB):
a, b = headA, headB
while a != b:
a = a.next if a else headB
b = b.next if b else headA
return a
# 时间 O(m+n),空间 O(1)
题目:每 K 个节点一组进行翻转。不足 K 个保持原序。
思路:先数长度确定有几组。每组内用标准反转,组间用 prev_tail 连接。
def reverseKGroup(head, k):
# 计算长度
length, curr = 0, head
while curr: length += 1; curr = curr.next
dummy = ListNode(0, head)
prev_group = dummy
for _ in range(length // k):
# 反转这一组
group_prev, curr = prev_group, prev_group.next
for _ in range(k):
nxt = curr.next
curr.next = group_prev
group_prev = curr
curr = nxt
# 连接前后
tail = prev_group.next # 反转后的尾
tail.next = curr
prev_group.next = group_prev # 反转后的头
prev_group = tail
return dummy.next
# 时间 O(n),空间 O(1)
题目:设计 LRU(最近最少使用)缓存,get 和 put 均为 O(1)。
思路:哈希表存 key→node 映射,双向链表维护访问顺序。最近访问的放头部,淘汰尾部。
class Node:
def __init__(self, key=0, val=0):
self.key, self.val = key, val
self.prev = self.next = None
class LRUCache:
def __init__(self, capacity):
self.cap = capacity
self.cache = {}
self.head, self.tail = Node(), Node() # 哨兵
self.head.next, self.tail.prev = self.tail, self.head
def _remove(self, node):
node.prev.next, node.next.prev = node.next, node.prev
def _add_to_head(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.cache: return -1
node = self.cache[key]
self._remove(node)
self._add_to_head(node)
return node.val
def put(self, key, value):
if key in self.cache:
self._remove(self.cache[key])
node = Node(key, value)
self.cache[key] = node
self._add_to_head(node)
if len(self.cache) > self.cap:
lru = self.tail.prev
self._remove(lru)
del self.cache[lru.key]
| # | 题目 | 难度 | 核心算法 |
|---|---|---|---|
| 20 | 有效的括号 | 🟢 简单 | 栈匹配 |
| 155 | 最小栈 | 🟡 中等 | 辅助栈 |
| 150 | 逆波兰表达式求值 | 🟡 中等 | 栈计算 |
| 739 | 每日温度 | 🟡 中等 | 单调栈 |
| 239 | 滑动窗口最大值 | 🔴 困难 | 单调队列 |
| 347 | 前 K 个高频元素 | 🟡 中等 | 哈希 + 堆 |
题目:判断括号字符串是否有效。如 "()[]{}" 有效,"(]" 无效。
思路:遇到左括号入栈,遇到右括号弹出栈顶检查是否匹配。
def isValid(s):
stack = []
mapping = {')': '(', ']': '[', '}': '{'}
for c in s:
if c in mapping:
if not stack or stack[-1] != mapping[c]:
return False
stack.pop()
else:
stack.append(c)
return not stack
# 时间 O(n),空间 O(n)
题目:设计一个栈,支持 push、pop、top 和 O(1) 时间获取最小值。
思路:用一个辅助栈同步记录当前栈中的最小值。
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = [] # 辅助栈,栈顶始终是最小值
def push(self, val):
self.stack.append(val)
if not self.min_stack or val <= self.min_stack[-1]:
self.min_stack.append(val)
def pop(self):
if self.stack.pop() == self.min_stack[-1]:
self.min_stack.pop()
def top(self): return self.stack[-1]
def getMin(self): return self.min_stack[-1]
题目:计算逆波兰表达式(后缀表达式)。如 ["2","1","+","3","*"] = (2+1)*3 = 9。
思路:遇到数字入栈,遇到运算符弹出两个数计算后压回。
def evalRPN(tokens):
stack = []
for t in tokens:
if t in '+-*/':
b, a = stack.pop(), stack.pop()
if t == '+': stack.append(a + b)
elif t == '-': stack.append(a - b)
elif t == '*': stack.append(a * b)
else: stack.append(int(a / b))
else:
stack.append(int(t))
return stack[0]
# 时间 O(n),空间 O(n)
题目:给定每天温度,找出每天要等多少天才能遇到更高温度。
思路:单调递减栈。栈中存下标。当当前温度大于栈顶时,弹出栈顶并计算等待天数。
def dailyTemperatures(temps):
n = len(temps)
result = [0] * n
stack = [] # 存下标,温度单调递减
for i in range(n):
while stack and temps[i] > temps[stack[-1]]:
j = stack.pop()
result[j] = i - j
stack.append(i)
return result
# 时间 O(n),空间 O(n)
题目:大小为 k 的滑动窗口从左到右移动,返回每个窗口的最大值。
思路:单调递减队列。队首始终是窗口最大值。窗口移动时,移除超出的元素,维护单调性。
from collections import deque
def maxSlidingWindow(nums, k):
dq = deque() # 存下标,对应值单调递减
result = []
for i in range(len(nums)):
# 移除超出窗口的元素
while dq and dq[0] < i - k + 1:
dq.popleft()
# 维护单调递减
while dq and nums[i] >= nums[dq[-1]]:
dq.pop()
dq.append(i)
if i >= k - 1:
result.append(nums[dq[0]])
return result
# 时间 O(n),空间 O(k)
题目:返回出现频率前 K 高的元素。
思路:哈希表统计频率,用大小为 K 的最小堆维护前 K 高。频率比堆顶大就替换。
def topKFrequent(nums, k):
from collections import Counter
import heapq
count = Counter(nums)
return heapq.nlargest(k, count.keys(), key=count.get)
# 时间 O(n log k),空间 O(n)
| # | 题目 | 难度 | 核心算法 |
|---|---|---|---|
| 94 | 二叉树的中序遍历 | 🟢 简单 | 递归/迭代 |
| 102 | 二叉树的层序遍历 | 🟡 中等 | BFS |
| 104 | 二叉树的最大深度 | 🟢 简单 | 递归 DFS |
| 226 | 翻转二叉树 | 🟢 简单 | 递归 |
| 101 | 对称二叉树 | 🟢 简单 | 递归/迭代 |
| 543 | 二叉树的直径 | 🟢 简单 | DFS 求最大路径 |
| 236 | 二叉树的最近公共祖先 | 🟡 中等 | 递归回溯 |
| 105 | 从前序与中序遍历构造二叉树 | 🟡 中等 | 递归分治 |
| 98 | 验证二叉搜索树 | 🟡 中等 | 中序遍历检查有序 |
| 230 | 二叉搜索树中第 K 小的元素 | 🟡 中等 | 中序遍历 |
题目:返回二叉树的中序遍历结果(左→根→右)。
思路:递归:先遍历左子树,访问根,再遍历右子树。迭代:用栈模拟。
def inorderTraversal(root):
result, stack = [], []
curr = root
while curr or stack:
while curr:
stack.append(curr)
curr = curr.left
curr = stack.pop()
result.append(curr.val)
curr = curr.right
return result
# 时间 O(n),空间 O(h)
题目:逐层从左到右遍历二叉树。
思路:BFS。用队列,每次处理当前层的所有节点,把子节点加入下一层。
from collections import deque
def levelOrder(root):
if not root: return []
result, queue = [], deque([root])
while queue:
level = []
for _ in range(len(queue)):
node = queue.popleft()
level.append(node.val)
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
result.append(level)
return result
# 时间 O(n),空间 O(n)
题目:返回二叉树的最大深度。
思路:递归。最大深度 = max(左子树深度, 右子树深度) + 1。
def maxDepth(root):
if not root: return 0
return max(maxDepth(root.left), maxDepth(root.right)) + 1
# 时间 O(n),空间 O(h)
题目:翻转二叉树的每个节点的左右子树。
思路:递归交换每个节点的左右子树。
def invertTree(root):
if not root: return None
root.left, root.right = invertTree(root.right), invertTree(root.left)
return root
# 时间 O(n),空间 O(h)
题目:判断二叉树是否镜像对称。
思路:递归比较左子树和右子树。左子树的左 = 右子树的右,左子树的右 = 右子树的左。
def isSymmetric(root):
def isMirror(t1, t2):
if not t1 and not t2: return True
if not t1 or not t2: return False
return t1.val == t2.val and isMirror(t1.left, t2.right) and isMirror(t1.right, t2.left)
return isMirror(root, root)
# 时间 O(n),空间 O(h)
题目:二叉树中任意两节点间最长路径的长度(边数)。
思路:DFS 求每个节点的最大深度。直径经过节点 i = 左深度 + 右深度。取全局最大值。
def diameterOfBinaryTree(root):
diameter = 0
def depth(node):
nonlocal diameter
if not node: return 0
left = depth(node.left)
right = depth(node.right)
diameter = max(diameter, left + right)
return max(left, right) + 1
depth(root)
return diameter
# 时间 O(n),空间 O(h)
题目:找到两个节点在树中的最近公共祖先(LCA)。
思路:递归。如果当前节点是 p 或 q,返回当前节点。如果左右子树各找到一个,当前节点就是 LCA。
def lowestCommonAncestor(root, p, q):
if not root or root == p or root == q:
return root
left = lowestCommonAncestor(root.left, p, q)
right = lowestCommonAncestor(root.right, p, q)
if left and right: return root # p 和 q 分布在两侧
return left or right
# 时间 O(n),空间 O(h)
题目:根据前序和中序遍历结果重建二叉树。
思路:前序第一个是根。在中序中找到根的位置,左边是左子树,右边是右子树。递归构建。
def buildTree(preorder, inorder):
if not preorder: return None
root_val = preorder[0]
root = TreeNode(root_val)
mid = inorder.index(root_val)
root.left = buildTree(preorder[1:mid+1], inorder[:mid])
root.right = buildTree(preorder[mid+1:], inorder[mid+1:])
return root
# 时间 O(n²)(用哈希优化到 O(n)),空间 O(n)
题目:判断一棵树是否是有效的 BST(左 < 根 < 右)。
思路:中序遍历 BST 应该是严格递增的。遍历过程中检查是否始终递增。
def isValidBST(root):
prev = float('-inf')
def inorder(node):
nonlocal prev
if not node: return True
if not inorder(node.left): return False
if node.val <= prev: return False
prev = node.val
return inorder(node.right)
return inorder(root)
# 时间 O(n),空间 O(h)
题目:在 BST 中找到第 K 小的元素。
思路:中序遍历 BST 得到有序序列。遍历到第 K 个就是答案。
def kthSmallest(root, k):
stack = []
curr = root
while curr or stack:
while curr:
stack.append(curr)
curr = curr.left
curr = stack.pop()
k -= 1
if k == 0: return curr.val
curr = curr.right
# 时间 O(H + k),空间 O(H)
| # | 题目 | 难度 | 核心算法 |
|---|---|---|---|
| 215 | 数组中的第 K 个最大元素 | 🟡 中等 | 快速选择/堆 |
| 295 | 数据流的中位数 | 🔴 困难 | 大顶堆 + 小顶堆 |
| 23 | 合并 K 个升序链表 | 🔴 困难 | 最小堆 |
| 347 | 前 K 个高频元素 | 🟡 中等 | 最小堆 |
| 703 | 数据流中的第 K 大元素 | 🟢 简单 | 大小为 K 的最小堆 |
题目:未排序数组中找到第 K 大的元素。
思路:维护大小为 K 的最小堆。遍历完后堆顶就是第 K 大。或用快速选择 O(n)。
def findKthLargest(nums, k):
import heapq
heap = nums[:k]
heapq.heapify(heap)
for num in nums[k:]:
if num > heap[0]:
heapq.heapreplace(heap, num)
return heap[0]
# 时间 O(n log k),空间 O(k)
题目:支持添加数字和获取中位数的数据结构。
思路:大顶堆存较小一半,小顶堆存较大一半。中位数 = 堆顶的平均或其中一个。
import heapq
class MedianFinder:
def __init__(self):
self.small = [] # 大顶堆(取负)
self.large = [] # 小顶堆
def addNum(self, num):
heapq.heappush(self.small, -num)
heapq.heappush(self.large, -heapq.heappop(self.small))
if len(self.large) > len(self.small):
heapq.heappush(self.small, -heapq.heappop(self.large))
def findMedian(self):
if len(self.small) > len(self.large):
return -self.small[0]
return (-self.small[0] + self.large[0]) / 2
题目:合并 K 个有序链表为一个有序链表。
思路:最小堆维护 K 个链表的当前头节点。每次取最小的接到结果链表,再把该链表的下一个节点入堆。
import heapq
def mergeKLists(lists):
heap = []
for i, l in enumerate(lists):
if l:
heapq.heappush(heap, (l.val, i, l))
dummy = curr = ListNode(0)
while heap:
val, i, node = heapq.heappop(heap)
curr.next = node
curr = curr.next
if node.next:
heapq.heappush(heap, (node.next.val, i, node.next))
return dummy.next
# 时间 O(N log K),N 是总节点数
题目:不断添加数字,维护第 K 大的元素。
思路:大小为 K 的最小堆。堆顶就是第 K 大。
import heapq
class KthLargest:
def __init__(self, k, nums):
self.k = k
self.heap = nums
heapq.heapify(self.heap)
while len(self.heap) > k:
heapq.heappop(self.heap)
def add(self, val):
heapq.heappush(self.heap, val)
if len(self.heap) > self.k:
heapq.heappop(self.heap)
return self.heap[0]
| # | 题目 | 难度 | 核心算法 |
|---|---|---|---|
| 200 | 岛屿数量 | 🟡 中等 | DFS/BFS 搜索 |
| 994 | 腐烂的橘子 | 🟡 中等 | 多源 BFS |
| 207 | 课程表 | 🟡 中等 | 拓扑排序 |
| 210 | 课程表 II | 🟡 中等 | 拓扑排序输出顺序 |
| 133 | 克隆图 | 🟡 中等 | BFS/DFS + 哈希 |
| 743 | 网络延迟时间 | 🟡 中等 | Dijkstra |
| 787 | K 站中转内最便宜的航班 | 🟡 中等 | Bellman-Ford / DP |
题目:网格中 '1' 是陆地,'0' 是水。数有多少个岛屿(上下左右连通)。
思路:遍历网格,遇到 '1' 就 DFS 把整个岛屿淹没(改为 '0'),计数 +1。
def numIslands(grid):
if not grid: return 0
count = 0
def dfs(i, j):
if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] != '1':
return
grid[i][j] = '0'
dfs(i+1, j); dfs(i-1, j); dfs(i, j+1); dfs(i, j-1)
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == '1':
dfs(i, j)
count += 1
return count
# 时间 O(M×N),空间 O(M×N)
题目:有先修关系的课程,判断能否修完所有课程(无环检测)。
思路:BFS 拓扑排序。计算入度,入度为 0 的课程可以修。修完后减少后续课程的入度。
from collections import deque, defaultdict
def canFinish(numCourses, prerequisites):
graph = defaultdict(list)
in_degree = [0] * numCourses
for a, b in prerequisites:
graph[b].append(a)
in_degree[a] += 1
queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
count = 0
while queue:
node = queue.popleft()
count += 1
for neighbor in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
return count == numCourses
# 时间 O(V+E),空间 O(V+E)
题目:n 个节点的有向加权图,从节点 K 出发,求到达所有节点的最短时间。
思路:标准 Dijkstra。用最小堆维护当前最近的节点。
import heapq
from collections import defaultdict
def networkDelayTime(times, n, k):
graph = defaultdict(list)
for u, v, w in times:
graph[u].append((v, w))
dist = {k: 0}
heap = [(0, k)]
while heap:
d, u = heapq.heappop(heap)
if d > dist.get(u, float('inf')): continue
for v, w in graph[u]:
if d + w < dist.get(v, float('inf')):
dist[v] = d + w
heapq.heappush(heap, (d + w, v))
return max(dist.values()) if len(dist) == n else -1
# 时间 O(E log V),空间 O(V+E)
题目:n 个城市,isConnected[i][j]=1 表示相连。求连通分量数。
思路:并查集。相连的城市合并,最后数不同的根节点数。
def findCircleNum(isConnected):
n = len(isConnected)
parent = list(range(n))
def find(x):
if parent[x] != x: parent[x] = find(parent[x])
return parent[x]
def union(x, y):
px, py = find(x), find(y)
if px != py: parent[px] = py
for i in range(n):
for j in range(i+1, n):
if isConnected[i][j]: union(i, j)
return len(set(find(i) for i in range(n)))
# 时间 O(n²),空间 O(n)
题目:一棵树多了一条边,找到这条冗余边。
思路:逐条加边,用并查集检查。如果两个端点已经在同一集合,这条边就是冗余的。
def findRedundantConnection(edges):
parent = list(range(len(edges) + 1))
def find(x):
if parent[x] != x: parent[x] = find(parent[x])
return parent[x]
for u, v in edges:
if find(u) == find(v): return [u, v]
parent[find(u)] = find(v)
# 时间 O(n·α(n)),空间 O(n)
题目:在有序数组中查找目标值,找到返回下标,否则返回 -1。
思路:标准二分。每次取中点比较,缩小一半范围。
def search(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target: return mid
elif nums[mid] < target: lo = mid + 1
else: hi = mid - 1
return -1
# 时间 O(log n),空间 O(1)
题目:在旋转后的有序数组(如 [4,5,6,7,0,1,2])中搜索目标值。
思路:二分。先判断哪半边是有序的,再决定搜索方向。
def search(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target: return mid
if nums[lo] <= nums[mid]: # 左半边有序
if nums[lo] <= target < nums[mid]: hi = mid - 1
else: lo = mid + 1
else: # 右半边有序
if nums[mid] < target <= nums[hi]: lo = mid + 1
else: hi = mid - 1
return -1
# 时间 O(log n),空间 O(1)
题目:找出不含重复字符的最长子串长度。
思路:滑动窗口 + 哈希集合。右指针扩展窗口,遇到重复时左指针收缩。
def lengthOfLongestSubstring(s):
seen = set()
lo = max_len = 0
for hi in range(len(s)):
while s[hi] in seen:
seen.remove(s[lo])
lo += 1
seen.add(s[hi])
max_len = max(max_len, hi - lo + 1)
return max_len
# 时间 O(n),空间 O(min(n, 字符集))
题目:字符串 s 中找到包含 t 所有字符的最短子串。
思路:滑动窗口 + 计数。右指针扩展直到包含所有字符,左指针收缩找最短。
from collections import Counter
def minWindow(s, t):
need = Counter(t)
missing = len(t)
lo = 0
start, end = 0, float('inf')
for hi in range(len(s)):
if need[s[hi]] > 0: missing -= 1
need[s[hi]] -= 1
while missing == 0: # 已包含所有字符
if hi - lo < end - lo:
start, end = lo, hi + 1
need[s[lo]] += 1
if need[s[lo]] > 0: missing += 1
lo += 1
return s[start:end] if end < float('inf') else ""
# 时间 O(n),空间 O(字符集)
| # | 题目 | 难度 | 核心算法 |
|---|---|---|---|
| 684 | 冗余连接 | 🟡 中等 | 并查集 |
| 547 | 省份数量 | 🟡 中等 | 并查集/DFS |
| 128 | 最长连续序列 | 🟡 中等 | 并查集/哈希 |
| 721 | 账户合并 | 🟡 中等 | 并查集 |
| # | 题目 | 难度 | 核心算法 |
|---|---|---|---|
| 704 | 二分查找 | 🟢 简单 | 标准二分 |
| 35 | 搜索插入位置 | 🟢 简单 | 二分找左边界 |
| 34 | 在排序数组中查找元素的第一个和最后一个位置 | 🟡 中等 | 左右边界二分 |
| 33 | 搜索旋转排序数组 | 🟡 中等 | 变体二分 |
| 153 | 寻找旋转排序数组中的最小值 | 🟡 中等 | 变体二分 |
| 4 | 寻找两个正序数组的中位数 | 🔴 困难 | 二分找第 K 小 |
| # | 题目 | 难度 | 核心算法 |
|---|---|---|---|
| 3 | 无重复字符的最长子串 | 🟡 中等 | 滑动窗口 + 哈希 |
| 76 | 最小覆盖子串 | 🔴 困难 | 滑动窗口 + 计数 |
| 438 | 找到字符串中所有字母异位词 | 🟡 中等 | 定长滑动窗口 |
| 209 | 长度最小的子数组 | 🟡 中等 | 滑动窗口求最短 |
| 567 | 字符串的排列 | 🟡 中等 | 定长滑动窗口 |
| # | 题目 | 难度 | 核心算法 |
|---|---|---|---|
| 912 | 排序数组 | 🟡 中等 | 快排/归并 |
| 56 | 合并区间 | 🟡 中等 | 排序 + 合并 |
| 148 | 排序链表 | 🟡 中等 | 归并排序 |
| 215 | 数组中的第 K 个最大元素 | 🟡 中等 | 快速选择 |
| 179 | 最大数 | 🟡 中等 | 自定义排序 |
题目:合并所有重叠的区间。
思路:按起始排序。如果当前区间和前一个重叠(start <= prev.end),合并。
def merge(intervals):
intervals.sort()
merged = [intervals[0]]
for start, end in intervals[1:]:
if start <= merged[-1][1]:
merged[-1][1] = max(merged[-1][1], end)
else:
merged.append([start, end])
return merged
# 时间 O(n log n),空间 O(n)
题目:对链表进行 O(n log n) 排序。
思路:归并排序。快慢指针找中点,递归排序两半,合并。
def sortList(head):
if not head or not head.next: return head
# 快慢指针找中点
slow, fast = head, head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
mid = slow.next
slow.next = None
# 递归排序两半
left = sortList(head)
right = sortList(mid)
# 合并
dummy = curr = ListNode(0)
while left and right:
if left.val <= right.val:
curr.next = left; left = left.next
else:
curr.next = right; right = right.next
curr = curr.next
curr.next = left or right
return dummy.next
# 时间 O(n log n),空间 O(log n)
| # | 题目 | 难度 | 核心算法 |
|---|---|---|---|
| 70 | 爬楼梯 | 🟢 简单 | 斐波那契 DP |
| 118 | 杨辉三角 | 🟢 简单 | 基础 DP |
| 198 | 打家劫舍 | 🟡 中等 | 线性 DP |
| 322 | 零钱兑换 | 🟡 中等 | 完全背包 |
| 300 | 最长递增子序列 | 🟡 中等 | DP / 贪心+二分 |
| 1143 | 最长公共子序列 | 🟡 中等 | 二维 DP |
| 72 | 编辑距离 | 🟡 中等 | 二维 DP |
| 139 | 单词拆分 | 🟡 中等 | DP + 哈希 |
| 152 | 乘积最大子数组 | 🟡 中等 | DP 维护最大最小 |
| 5 | 最长回文子串 | 🟡 中等 | 中心扩展 / DP |
| 647 | 回文子串 | 🟡 中等 | 中心扩展 |
| 416 | 分割等和子集 | 🟡 中等 | 0-1 背包 |
| 32 | 最长有效括号 | 🔴 困难 | 栈 / DP |
题目:每次可以爬 1 或 2 阶,求到第 n 阶有多少种方法。
思路:f(n) = f(n-1) + f(n-2),斐波那契数列。空间优化为两个变量。
def climbStairs(n):
a, b = 1, 1
for _ in range(n):
a, b = b, a + b
return a
# 时间 O(n),空间 O(1)
题目:不能同时抢相邻的房子。求最大收益。
思路:dp[i] = max(dp[i-1], dp[i-2] + nums[i])。选或不选当前房子。
def rob(nums):
prev, curr = 0, 0
for num in nums:
prev, curr = curr, max(curr, prev + num)
return curr
# 时间 O(n),空间 O(1)
题目:用给定硬币凑出金额 amount 的最少硬币数。
思路:完全背包。dp[i] = min(dp[i], dp[i-coin] + 1)。
def coinChange(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for i in range(1, amount + 1):
for coin in coins:
if coin <= i:
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
# 时间 O(amount × coins),空间 O(amount)
题目:找到未排序数组中最长严格递增子序列的长度。
思路:贪心 + 二分。维护一个数组 tails,tails[i] 是长度为 i+1 的递增子序列的最小末尾。
import bisect
def lengthOfLIS(nums):
tails = []
for num in nums:
pos = bisect.bisect_left(tails, num)
if pos == len(tails):
tails.append(num)
else:
tails[pos] = num
return len(tails)
# 时间 O(n log n),空间 O(n)
题目:找到字符串中最长的回文子串。
思路:中心扩展法。以每个字符(和每两个字符之间)为中心,向两边扩展找最长回文。
def longestPalindrome(s):
def expand(l, r):
while l >= 0 and r < len(s) and s[l] == s[r]:
l -= 1; r += 1
return s[l+1:r]
result = ""
for i in range(len(s)):
odd = expand(i, i)
even = expand(i, i + 1)
result = max(result, odd, even, key=len)
return result
# 时间 O(n²),空间 O(1)
题目:判断能否将数组分成两个子集,使和相等。
思路:0-1 背包。目标容量 = sum/2。dp[j] 表示能否凑出和 j。
def canPartition(nums):
total = sum(nums)
if total % 2: return False
target = total // 2
dp = [False] * (target + 1)
dp[0] = True
for num in nums:
for j in range(target, num - 1, -1): # 逆序!
dp[j] = dp[j] or dp[j - num]
return dp[target]
# 时间 O(n × target),空间 O(target)
题目:找到乘积最大的连续子数组。
思路:同时维护最大值和最小值(负数×负数=正数)。
def maxProduct(nums):
max_prod = min_prod = result = nums[0]
for num in nums[1:]:
candidates = (num, max_prod * num, min_prod * num)
max_prod = max(candidates)
min_prod = min(candidates)
result = max(result, max_prod)
return result
# 时间 O(n),空间 O(1)
| # | 题目 | 难度 | 核心算法 |
|---|---|---|---|
| 55 | 跳跃游戏 | 🟡 中等 | 贪心维护最远可达 |
| 45 | 跳跃游戏 II | 🟡 中等 | 贪心最少步数 |
| 452 | 用最少数量的箭引爆气球 | 🟡 中等 | 区间贪心 |
| 435 | 无重叠区间 | 🟡 中等 | 按结束时间贪心 |
| 763 | 划分字母区间 | 🟡 中等 | 贪心分割 |
| 122 | 买卖股票的最佳时机 II | 🟡 中等 | 贪心累加正收益 |
题目:数组每个元素是最大跳跃步数,判断能否到达最后一个位置。
思路:贪心维护当前能到达的最远位置。如果最远位置 >= 末尾则可达。
def canJump(nums):
max_reach = 0
for i in range(len(nums)):
if i > max_reach: return False
max_reach = max(max_reach, i + nums[i])
return True
# 时间 O(n),空间 O(1)
题目:可以多次买卖,求最大利润。
思路:贪心:所有上涨的区间都参与。累加所有正收益。
def maxProfit(prices):
profit = 0
for i in range(1, len(prices)):
if prices[i] > prices[i-1]:
profit += prices[i] - prices[i-1]
return profit
# 时间 O(n),空间 O(1)
题目:移除最少的区间使剩余区间不重叠。
思路:按结束时间排序。选结束最早的区间,贪心地给后续留最多空间。
def eraseOverlapIntervals(intervals):
intervals.sort(key=lambda x: x[1])
count, end = 0, float('-inf')
for s, e in intervals:
if s >= end:
end = e
else:
count += 1 # 移除当前区间
return count
# 时间 O(n log n),空间 O(1)
| # | 题目 | 难度 | 核心算法 |
|---|---|---|---|
| 46 | 全排列 | 🟡 中等 | 回溯 |
| 78 | 子集 | 🟡 中等 | 回溯 |
| 39 | 组合总和 | 🟡 中等 | 回溯 + 剪枝 |
| 22 | 括号生成 | 🟡 中等 | 回溯 |
| 79 | 单词搜索 | 🟡 中等 | DFS 回溯 |
| 51 | N 皇后 | 🔴 困难 | 回溯 + 剪枝 |
| 17 | 电话号码的字母组合 | 🟡 中等 | 回溯枚举 |
| 131 | 分割回文串 | 🟡 中等 | 回溯 + DP 判断 |
题目:返回数组的所有全排列。
思路:回溯。每步选一个未使用的数加入路径,用完回退。
def permute(nums):
result = []
def backtrack(path, used):
if len(path) == len(nums):
result.append(path[:])
return
for i in range(len(nums)):
if used[i]: continue
used[i] = True
path.append(nums[i])
backtrack(path, used)
path.pop()
used[i] = False
backtrack([], [False] * len(nums))
return result
# 时间 O(n! × n),空间 O(n)
题目:返回数组的所有子集。
思路:回溯。每个元素选或不选。
def subsets(nums):
result = []
def backtrack(start, path):
result.append(path[:])
for i in range(start, len(nums)):
path.append(nums[i])
backtrack(i + 1, path)
path.pop()
backtrack(0, [])
return result
# 时间 O(2^n × n),空间 O(n)
题目:找出所有和为 target 的组合(数字可重复使用)。
思路:回溯 + 剪枝。排序后,如果当前数已超过 target 就剪枝。
def combinationSum(candidates, target):
result = []
candidates.sort()
def backtrack(start, path, remain):
if remain == 0:
result.append(path[:])
return
for i in range(start, len(candidates)):
if candidates[i] > remain: break
path.append(candidates[i])
backtrack(i, path, remain - candidates[i]) # i 不是 i+1(可重复)
path.pop()
backtrack(0, [], target)
return result
题目:生成所有有效的 n 对括号组合。
思路:回溯。左括号数不超过 n,右括号数不超过左括号数。
def generateParenthesis(n):
result = []
def backtrack(path, left, right):
if len(path) == 2 * n:
result.append(path)
return
if left < n:
backtrack(path + '(', left + 1, right)
if right < left:
backtrack(path + ')', left, right + 1)
backtrack('', 0, 0)
return result
# 时间 O(4^n / √n),空间 O(n)
题目:给定数字字符串,返回所有可能的字母组合(手机键盘映射)。
思路:回溯。每个数字对应若干字母,逐位枚举。
def letterCombinations(digits):
if not digits: return []
mapping = {'2':'abc','3':'def','4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz'}
result = []
def backtrack(i, path):
if i == len(digits):
result.append(path); return
for c in mapping[digits[i]]:
backtrack(i + 1, path + c)
backtrack(0, "")
return result
题目:将字符串分割成所有片段都是回文的方案。
思路:回溯枚举分割位置,用 DP 预处理判断子串是否回文。
def partition(s):
n = len(s)
# 预处理:is_pal[i][j] = s[i..j] 是否回文
is_pal = [[True]*n for _ in range(n)]
for i in range(n-1,-1,-1):
for j in range(i+1,n):
is_pal[i][j] = s[i]==s[j] and is_pal[i+1][j-1]
result = []
def backtrack(start, path):
if start == n:
result.append(path[:]); return
for end in range(start, n):
if is_pal[start][end]:
path.append(s[start:end+1])
backtrack(end+1, path)
path.pop()
backtrack(0, [])
return result
题目:在 N×N 棋盘上放 N 个皇后,互不攻击。
思路:回溯逐行放置。用三个集合记录已占用的列、主对角线、副对角线。
def solveNQueens(n):
result = []
def backtrack(row, cols, diag1, diag2, board):
if row == n:
result.append([''.join(r) for r in board])
return
for col in range(n):
if col in cols or row-col in diag1 or row+col in diag2:
continue
board[row][col] = 'Q'
backtrack(row+1, cols|{col}, diag1|{row-col}, diag2|{row+col}, board)
board[row][col] = '.'
backtrack(0, set(), set(), set(), [['.']*n for _ in range(n)])
return result
| # | 题目 | 难度 | 核心算法 |
|---|---|---|---|
| 5 | 最长回文子串 | 🟡 中等 | 中心扩展 / Manacher |
| 28 | 找出字符串中第一个匹配项的下标 | 🟢 简单 | KMP |
| 242 | 有效的字母异位词 | 🟢 简单 | 计数 |
| 49 | 字母异位词分组 | 🟡 中等 | 排序 + 哈希 |
| 125 | 验证回文串 | 🟢 简单 | 双指针 |
| 647 | 回文子串 | 🟡 中等 | 中心扩展 |
题目:在 haystack 中找 needle 第一次出现的位置。
思路:KMP 算法。构建 next 数组后线性扫描。Python 可直接用 find()。
def strStr(haystack, needle):
return haystack.find(needle)
# 或用 KMP(见第 19 章实现)
题目:判断字符串是否是回文(只考虑字母和数字)。
思路:双指针从两端向中间。跳过非字母数字字符。
def isPalindrome(s):
lo, hi = 0, len(s) - 1
while lo < hi:
while lo < hi and not s[lo].isalnum(): lo += 1
while lo < hi and not s[hi].isalnum(): hi -= 1
if s[lo].lower() != s[hi].lower(): return False
lo += 1; hi -= 1
return True
# 时间 O(n),空间 O(1)
题目:统计字符串中回文子串的数目。
思路:中心扩展。每个字符和每两个字符之间都作为中心扩展。
def countSubstrings(s):
count = 0
for center in range(2 * len(s) - 1):
lo = center // 2
hi = lo + center % 2
while lo >= 0 and hi < len(s) and s[lo] == s[hi]:
count += 1; lo -= 1; hi += 1
return count
# 时间 O(n²),空间 O(1)
| # | 题目 | 难度 | 核心算法 |
|---|---|---|---|
| 136 | 只出现一次的数字 | 🟢 简单 | 异或 |
| 191 | 位1的个数 | 🟢 简单 | 位运算 |
| 338 | 比特位计数 | 🟢 简单 | DP + 位运算 |
| 461 | 汉明距离 | 🟢 简单 | 异或 + 计数 |
| 50 | Pow(x, n) | 🟡 中等 | 快速幂 |
| 172 | 阶乘后的零 | 🟡 中等 | 数学(数因子5) |
题目:其他数都出现两次,只有一个数出现一次。找出它。
思路:异或。a^a=0,a^0=a。所有数异或后只剩出现一次的数。
def singleNumber(nums):
result = 0
for num in nums:
result ^= num
return result
# 时间 O(n),空间 O(1)
题目:实现 pow(x, n),即 x^n。
思路:快速幂。n 为偶数时 x^n = (x²)^(n/2),n 为奇数时多乘一个 x。
def myPow(x, n):
if n < 0: x, n = 1/x, -n
result = 1
while n:
if n % 2: result *= x
x *= x
n //= 2
return result
# 时间 O(log n),空间 O(1)
| # | 题目 | 难度 | 核心算法 |
|---|---|---|---|
| 560 | 和为 K 的子数组 | 🟡 中等 | 前缀和 + 哈希 |
| 303 | 区域和检索 - 数组不可变 | 🟢 简单 | 前缀和 |
| 304 | 二维区域和检索 | 🟡 中等 | 二维前缀和 |
| 1109 | 航班预订统计 | 🟡 中等 | 差分数组 |
| 525 | 连续数组 | 🟡 中等 | 前缀和 + 哈希 |
题目:找出和为 k 的连续子数组个数。
思路:前缀和 + 哈希。如果 prefix[j] - prefix[i] = k,则 i..j 的和为 k。用哈希记录每个前缀和出现的次数。
def subarraySum(nums, k):
from collections import defaultdict
count = 0
prefix = 0
seen = defaultdict(int)
seen[0] = 1
for num in nums:
prefix += num
count += seen[prefix - k]
seen[prefix] += 1
return count
# 时间 O(n),空间 O(n)
| # | 题目 | 难度 | 核心算法 |
|---|---|---|---|
| 496 | 下一个更大元素 I | 🟢 简单 | 单调栈 |
| 503 | 下一个更大元素 II | 🟡 中等 | 循环单调栈 |
| 84 | 柱状图中最大的矩形 | 🔴 困难 | 单调栈 |
| 42 | 接雨水 | 🔴 困难 | 单调栈 / 双指针 |
| 239 | 滑动窗口最大值 | 🔴 困难 | 单调队列 |
题目:柱状图能接多少雨水。
思路:双指针。每个位置的水量 = min(左边最高, 右边最高) - 当前高度。
def trap(height):
lo, hi = 0, len(height) - 1
left_max = right_max = water = 0
while lo < hi:
if height[lo] < height[hi]:
if height[lo] >= left_max:
left_max = height[lo]
else:
water += left_max - height[lo]
lo += 1
else:
if height[hi] >= right_max:
right_max = height[hi]
else:
water += right_max - height[hi]
hi -= 1
return water
# 时间 O(n),空间 O(1)
题目:找到柱状图中最大矩形的面积。
思路:单调递增栈。当遇到更矮的柱子时,弹出栈顶并计算以它为高度的最大面积。
def largestRectangleArea(heights):
stack = [-1] # 哨兵
max_area = 0
for i, h in enumerate(heights):
while stack[-1] != -1 and heights[stack[-1]] >= h:
height = heights[stack.pop()]
width = i - stack[-1] - 1
max_area = max(max_area, height * width)
stack.append(i)
while stack[-1] != -1:
height = heights[stack.pop()]
width = len(heights) - stack[-1] - 1
max_area = max(max_area, height * width)
return max_area
# 时间 O(n),空间 O(n)
| # | 题目 | 难度 | 核心算法 |
|---|---|---|---|
| 200 | 岛屿数量 | 🟡 中等 | DFS/BFS |
| 695 | 岛屿的最大面积 | 🟡 中等 | DFS |
| 463 | 岛屿的周长 | 🟢 简单 | 遍历判断边界 |
| 130 | 被围绕的区域 | 🟡 中等 | 边界 DFS |
| 417 | 太平洋大西洋水流问题 | 🟡 中等 | 多源 DFS |
| 127 | 单词接龙 | 🔴 困难 | BFS 最短路径 |
题目:找到网格中最大岛屿的面积。
思路:DFS。遇到 '1' 就扩展整个岛屿并计数,取最大值。
def maxAreaOfIsland(grid):
max_area = 0
def dfs(i, j):
if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] == 0:
return 0
grid[i][j] = 0
return 1 + dfs(i+1,j) + dfs(i-1,j) + dfs(i,j+1) + dfs(i,j-1)
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == 1:
max_area = max(max_area, dfs(i, j))
return max_area
# 时间 O(M×N),空间 O(M×N)
题目:从 beginWord 到 endWord,每次改一个字母,求最短转换序列长度。
思路:BFS。每一步尝试改变每个位置的每个字母,找到在字典中的新词。
from collections import deque
def ladderLength(beginWord, endWord, wordList):
word_set = set(wordList)
if endWord not in word_set: return 0
queue = deque([(beginWord, 1)])
visited = {beginWord}
while queue:
word, steps = queue.popleft()
for i in range(len(word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
new_word = word[:i] + c + word[i+1:]
if new_word == endWord: return steps + 1
if new_word in word_set and new_word not in visited:
visited.add(new_word)
queue.append((new_word, steps + 1))
return 0
# 时间 O(M² × N),M 是单词长度,N 是词表大小
题目:最多 K 次中转,求最便宜价格。
思路:Bellman-Ford DP。dp[k][v] = 最多 k 次中转到 v 的最小费用。
def findCheapestPrice(n, flights, src, dst, k):
dp = [float('inf')] * n; dp[src] = 0
for _ in range(k + 1):
new_dp = dp[:]
for u, v, p in flights:
if dp[u] + p < new_dp[v]: new_dp[v] = dp[u] + p
dp = new_dp
return dp[dst] if dp[dst] != float('inf') else -1
题目:对数组排序。
思路:快速排序。选 pivot 分三组,递归拼接。
def sortArray(nums):
if len(nums) <= 1: return nums
pivot = nums[len(nums)//2]
return sortArray([x for x in nums if xpivot])
题目:到达末尾的最少跳跃次数。
思路:贪心。维护当前跳的边界和下一跳最远位置。
def jump(nums):
jumps = cur_end = farthest = 0
for i in range(len(nums)-1):
farthest = max(farthest, i + nums[i])
if i == cur_end:
jumps += 1; cur_end = farthest
return jumps
题目:在网格中搜索单词。
思路:DFS 回溯。标记已访问,回溯时恢复。
def exist(board, word):
m, n = len(board), len(board[0])
def dfs(i, j, k):
if k == len(word): return True
if i<0 or i>=m or j<0 or j>=n or board[i][j]!=word[k]: return False
tmp, board[i][j] = board[i][j], '#'
found = dfs(i+1,j,k+1) or dfs(i-1,j,k+1) or dfs(i,j+1,k+1) or dfs(i,j-1,k+1)
board[i][j] = tmp
return found
return any(dfs(i,j,0) for i in range(m) for j in range(n))
核心:n & (n-1) 消除最低位 1。#191 数 1 个数,#338 用 DP dp[i]=dp[i>>1]+(i&1),#461 异或后数 1。
def hammingWeight(n):
c = 0
while n: n &= n-1; c += 1
return c
def countBits(n):
dp = [0]*(n+1)
for i in range(1,n+1): dp[i] = dp[i>>1] + (i&1)
return dp
def hammingDistance(x, y): return bin(x^y).count('1')
核心:前缀和。一维:prefix[i+1] = prefix[i] + nums[i]。二维:容斥原理。
class NumArray:
def __init__(self, nums):
self.p = [0]
for x in nums: self.p.append(self.p[-1]+x)
def sumRange(self, l, r): return self.p[r+1] - self.p[l]
class NumMatrix:
def __init__(self, matrix):
m, n = len(matrix), len(matrix[0])
self.p = [[0]*(n+1) for _ in range(m+1)]
for i in range(m):
for j in range(n):
self.p[i+1][j+1] = matrix[i][j]+self.p[i][j+1]+self.p[i+1][j]-self.p[i][j]
def sumRegion(self, r1, c1, r2, c2):
return self.p[r2+1][c2+1]-self.p[r1][c2+1]-self.p[r2+1][c1]+self.p[r1][c1]
题目:bookings[i]=[first,last,seats],返回每个站点的总预订座位数。
思路:差分数组。区间 [first,last] 加 val:diff[first]+=val, diff[last+1]-=val。最后前缀和还原。
def corpFlightBookings(bookings, n):
diff = [0] * (n + 1)
for first, last, seats in bookings:
diff[first-1] += seats
diff[last] -= seats
result = []
curr = 0
for i in range(n):
curr += diff[i]
result.append(curr)
return result
核心:单调递减栈。从右往左遍历,维护栈中元素单调递减。
def nextGreaterElement(nums1, nums2):
stack, m = [], {}
for num in nums2:
while stack and stack[-1] < num: m[stack.pop()] = num
stack.append(num)
return [m.get(x, -1) for x in nums1]
核心:从边界开始 DFS。#130:边界 O 标记为安全。#417:太平洋和大西洋分别 DFS,交集为答案。
# #130 被围绕的区域
def solve(board):
m, n = len(board), len(board[0])
def dfs(i, j):
if 0<=i
题目:两个有序数组,找合并后的中位数。要求 O(log(m+n))。
思路:二分找第 K 小。每次排除 k/2 个元素。
def findMedianSortedArrays(nums1, nums2):
def findKth(k, a, b):
if a >= len(nums1): return nums2[b + k]
if b >= len(nums2): return nums1[a + k]
if k == 0: return min(nums1[a], nums2[b])
av = nums1[a + k//2] if a + k//2 < len(nums1) else float('inf')
bv = nums2[b + k//2] if b + k//2 < len(nums2) else float('inf')
if av < bv: return findKth(k - k//2, a + k//2 + 1, b)
else: return findKth(k - k//2, a, b + k//2 + 1)
total = len(nums1) + len(nums2)
if total % 2: return findKth(total//2, 0, 0)
return (findKth(total//2-1, 0, 0) + findKth(total//2, 0, 0)) / 2
题目:找到最长有效括号子串的长度。
思路:栈存下标。栈底放 -1 作为基准。遇到 ')' 弹栈后,当前下标 - 栈顶下标就是长度。
def longestValidParentheses(s):
stack = [-1]
max_len = 0
for i, c in enumerate(s):
if c == '(':
stack.append(i)
else:
stack.pop()
if not stack:
stack.append(i)
else:
max_len = max(max_len, i - stack[-1])
return max_len
题目:找到 target 的起始和结束位置。
思路:两次二分:找左边界和右边界。
def searchRange(nums, target):
def bisect_left(nums, target):
lo, hi = 0, len(nums)
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] < target: lo = mid + 1
else: hi = mid
return lo
left = bisect_left(nums, target)
right = bisect_left(nums, target + 1)
if left == right: return [-1, -1]
return [left, right - 1]
题目:找到 target 的索引,不存在返回应插入位置。
思路:标准二分。找不到时 lo 即插入位置。
def searchInsert(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target: return mid
elif nums[mid] < target: lo = mid + 1
else: hi = mid - 1
return lo
题目:将 word1 转换成 word2 的最少操作数(插入/删除/替换)。
思路:二维 DP。dp[i][j] = word1[:i] 变 word2[:j] 的最少操作。
def minDistance(word1, word2):
m, n = len(word1), len(word2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(m+1): dp[i][0] = i
for j in range(n+1): dp[0][j] = j
for i in range(1, m+1):
for j in range(1, n+1):
if word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
return dp[m][n]
题目:生成杨辉三角的前 numRows 行。
思路:每行首尾为 1,中间 = 上一行左+右。
def generate(numRows):
triangle = [[1]]
for i in range(1, numRows):
row = [1]
for j in range(1, i):
row.append(triangle[i-1][j-1] + triangle[i-1][j])
row.append(1)
triangle.append(row)
return triangle
题目:深拷贝一个图。
思路:DFS + 哈希表记录已克隆的节点,避免重复克隆。
def cloneGraph(node):
if not node: return None
cloned = {}
def dfs(n):
if n in cloned: return cloned[n]
copy = Node(n.val)
cloned[n] = copy
for neighbor in n.neighbors:
copy.neighbors.append(dfs(neighbor))
return copy
return dfs(node)
题目:判断字符串是否可以被拆分为字典中的单词。
思路:DP。dp[i] = s[:i] 是否可拆分。dp[i] = any(dp[j] and s[j:i] in wordDict)
def wordBreak(s, wordDict):
word_set = set(wordDict)
dp = [False] * (len(s) + 1)
dp[0] = True
for i in range(1, len(s) + 1):
for j in range(i):
if dp[j] and s[j:i] in word_set:
dp[i] = True
break
return dp[len(s)]
题目:旋转排序数组中找最小值。
思路:二分。nums[mid] > nums[hi] 则最小在右半边,否则在左半边。
def findMin(nums):
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] > nums[hi]: lo = mid + 1
else: hi = mid
return nums[lo]
题目:返回 n! 结果中尾随零的个数。
思路:数因子 5 的个数(2 比 5 多)。n/5 + n/25 + n/125 + ...
def trailingZeroes(n):
count = 0
while n >= 5:
n //= 5
count += n
return count
题目:排列数组中的数,使拼接后的数最大。
思路:自定义排序。比较 a+b vs b+a 哪个更大。
def largestNumber(nums):
from functools import cmp_to_key
nums_str = [str(n) for n in nums]
nums_str.sort(key=cmp_to_key(lambda a, b: int(b+a) - int(a+b)))
result = ''.join(nums_str)
return '0' if result[0] == '0' else result
题目:找到和 >= target 的最短连续子数组长度。
思路:滑动窗口。右指针扩展直到和 >= target,左指针收缩找最短。
def minSubArrayLen(target, nums):
lo = total = 0
min_len = float('inf')
for hi in range(len(nums)):
total += nums[hi]
while total >= target:
min_len = min(min_len, hi - lo + 1)
total -= nums[lo]
lo += 1
return min_len if min_len < float('inf') else 0
题目:返回修完所有课程的顺序(拓扑排序)。
思路:BFS 拓扑排序。入度为 0 的入队,逐步减少后续课程入度。
from collections import deque, defaultdict
def findOrder(numCourses, prerequisites):
graph = defaultdict(list)
in_degree = [0] * numCourses
for a, b in prerequisites:
graph[b].append(a); in_degree[a] += 1
queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
order = []
while queue:
node = queue.popleft()
order.append(node)
for nei in graph[node]:
in_degree[nei] -= 1
if in_degree[nei] == 0: queue.append(nei)
return order if len(order) == numCourses else []
题目:在 s 中找到所有 p 的异位词的起始索引。
思路:定长滑动窗口。维护窗口内字符计数和 p 的计数比较。
from collections import Counter
def findAnagrams(s, p):
if len(s) < len(p): return []
pc = Counter(p)
sc = Counter(s[:len(p)-1])
result = []
for i in range(len(p)-1, len(s)):
sc[s[i]] += 1
if sc == pc: result.append(i - len(p) + 1)
sc[s[i - len(p) + 1]] -= 1
if sc[s[i - len(p) + 1]] == 0: del sc[s[i - len(p) + 1]]
return result
题目:每个气球是一个区间,一支箭可以引爆重叠的所有气球。求最少箭数。
思路:按结束排序。如果当前气球起始 > 上一支箭的位置,需要新箭。
def findMinArrowShots(points):
points.sort(key=lambda x: x[1])
arrows = 1
end = points[0][1]
for s, e in points[1:]:
if s > end:
arrows += 1; end = e
return arrows
题目:计算网格中岛屿的周长。
思路:每个陆地格子贡献 4 条边,相邻的陆地减 2 条边。
def islandPerimeter(grid):
perimeter = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == 1:
perimeter += 4
if i > 0 and grid[i-1][j] == 1: perimeter -= 2
if j > 0 and grid[i][j-1] == 1: perimeter -= 2
return perimeter
题目:找到含有相同数量 0 和 1 的最长连续子数组。
思路:把 0 看作 -1。问题变为找和为 0 的最长子数组。前缀和 + 哈希。
def findMaxLength(nums):
seen = {0: -1}
prefix = max_len = 0
for i, num in enumerate(nums):
prefix += 1 if num == 1 else -1
if prefix in seen:
max_len = max(max_len, i - seen[prefix])
else:
seen[prefix] = i
return max_len
题目:判断 s2 是否包含 s1 的排列。
思路:定长滑动窗口。窗口长度 = len(s1),比较字符计数。
from collections import Counter
def checkInclusion(s1, s2):
if len(s1) > len(s2): return False
pc = Counter(s1)
sc = Counter(s2[:len(s1)])
if sc == pc: return True
for i in range(len(s1), len(s2)):
sc[s2[i]] += 1
sc[s2[i - len(s1)]] -= 1
if sc[s2[i - len(s1)]] == 0: del sc[s2[i - len(s1)]]
if sc == pc: return True
return False
题目:将字符串划分为尽可能多的片段,每个字母最多出现在一个片段中。
思路:贪心。先记录每个字母最后出现的位置。遍历时维护当前片段的最远边界。
def partitionLabels(s):
last = {c: i for i, c in enumerate(s)}
result = []
start = end = 0
for i, c in enumerate(s):
end = max(end, last[c])
if i == end:
result.append(end - start + 1)
start = end + 1
return result
题目:每分钟腐烂的橘子会感染上下左右的新鲜橘子。求所有橘子腐烂的最短时间。
思路:多源 BFS。所有腐烂橘子同时入队,逐层扩展。
from collections import deque
def orangesRotting(grid):
m, n = len(grid), len(grid[0])
queue = deque()
fresh = 0
for i in range(m):
for j in range(n):
if grid[i][j] == 2: queue.append((i, j))
elif grid[i][j] == 1: fresh += 1
if fresh == 0: return 0
minutes = 0
while queue:
for _ in range(len(queue)):
i, j = queue.popleft()
for di, dj in [(0,1),(0,-1),(1,0),(-1,0)]:
ni, nj = i+di, j+dj
if 0<=ni
题目:求两个字符串的最长公共子序列长度。
思路:二维 DP。dp[i][j] = text1[:i] 和 text2[:j] 的 LCS 长度。
def longestCommonSubsequence(text1, text2):
m, n = len(text1), len(text2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if text1[i-1] == text2[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[m][n]
第一周:数组 + 哈希 + 链表(15 题)→ 第二周:栈队列 + 树(15 题)→ 第三周:二分 + 滑动窗口 + 排序(15 题)→ 第四周:DP(15 题)→ 第五周:贪心 + 回溯(15 题)→ 第六周:图 + 并查集 + 综合(25 题)。每天 2-3 题,6 周刷完。
如果时间紧张,优先刷这 20 题:两数之和、反转链表、有效的括号、合并两个有序链表、二叉树最大深度、最大子数组和、爬楼梯、合并区间、买卖股票最佳时机、环形链表、LRU 缓存、无重复字符最长子串、三数之和、搜索旋转排序数组、岛屿数量、全排列、最长递增子序列、编辑距离、接雨水、最小覆盖子串。
Transformer 是现代 AI 的基石——GPT、BERT、Llama、Claude 全都基于它。理解 Transformer 的算法细节,是理解大模型的前提。
你在读一篇文章。传统方法(RNN)是从头到尾一个字一个字读,读到后面可能忘了前面。Transformer 的做法:读每个字时,同时看一遍全文的所有字,给每个字打一个"相关性分数",然后根据分数加权汇总信息。这就是注意力机制——"该关注哪里"。
注意力的核心公式:
import torch
import torch.nn.functional as F
import math
def scaled_dot_product_attention(Q, K, V, mask=None):
"""
Scaled Dot-Product Attention
Q: [batch, heads, seq_len, d_k]
K: [batch, heads, seq_len, d_k]
V: [batch, heads, seq_len, d_v]
"""
d_k = Q.shape[-1]
# 1. 计算注意力分数
scores = Q @ K.transpose(-2, -1) / math.sqrt(d_k)
# 2. 应用掩码(因果掩码或填充掩码)
if mask is not None:
scores = scores.masked_fill(mask == 0, float('-inf'))
# 3. Softmax 归一化
attn_weights = F.softmax(scores, dim=-1)
# 4. 加权求和
return attn_weights @ V, attn_weights
# 示例
batch, heads, seq_len, d_k = 2, 8, 10, 64
Q = torch.randn(batch, heads, seq_len, d_k)
K = torch.randn(batch, heads, seq_len, d_k)
V = torch.randn(batch, heads, seq_len, d_k)
output, weights = scaled_dot_product_attention(Q, K, V)
print(f"输出形状: {output.shape}") # [2, 8, 10, 64]
print(f"注意力权重形状: {weights.shape}") # [2, 8, 10, 10]
多头注意力:把 Q/K/V 分成多个"头",每个头独立计算注意力,最后拼接。不同头可以关注不同类型的模式(语法、语义、位置等)。
class MultiHeadAttention(torch.nn.Module):
def __init__(self, d_model=512, n_heads=8):
super().__init__()
self.d_model = d_model
self.n_heads = n_heads
self.d_k = d_model // n_heads
self.W_Q = torch.nn.Linear(d_model, d_model)
self.W_K = torch.nn.Linear(d_model, d_model)
self.W_V = torch.nn.Linear(d_model, d_model)
self.W_O = torch.nn.Linear(d_model, d_model)
def forward(self, Q, K, V, mask=None):
batch_size = Q.shape[0]
# 线性投影 + 分头
Q = self.W_Q(Q).view(batch_size, -1, self.n_heads, self.d_k).transpose(1, 2)
K = self.W_K(K).view(batch_size, -1, self.n_heads, self.d_k).transpose(1, 2)
V = self.W_V(V).view(batch_size, -1, self.n_heads, self.d_k).transpose(1, 2)
# 计算注意力
attn_output, _ = scaled_dot_product_attention(Q, K, V, mask)
# 拼接 + 输出投影
attn_output = attn_output.transpose(1, 2).contiguous().view(batch_size, -1, self.d_model)
return self.W_O(attn_output)
# 使用
mha = MultiHeadAttention(d_model=512, n_heads=8)
x = torch.randn(2, 10, 512) # batch=2, seq_len=10, d_model=512
output = mha(x, x, x) # 自注意力:Q=K=V=x
print(f"输出形状: {output.shape}") # [2, 10, 512]
GPT 等自回归模型使用因果掩码:每个 token 只能看到自己和之前的 token,不能看到未来。
def create_causal_mask(seq_len):
"""下三角掩码:token i 只能看到 0..i"""
mask = torch.tril(torch.ones(seq_len, seq_len))
return mask # 1 = 可以看到, 0 = 不能看到
mask = create_causal_mask(5)
print(mask)
# tensor([[1, 0, 0, 0, 0],
# [1, 1, 0, 0, 0],
# [1, 1, 1, 0, 0],
# [1, 1, 1, 1, 0],
# [1, 1, 1, 1, 1]])
Transformer 没有递归结构,需要额外注入位置信息。
# 正弦位置编码实现
import math
def sinusoidal_position_encoding(seq_len, d_model):
pe = torch.zeros(seq_len, d_model)
position = torch.arange(seq_len).unsqueeze(1).float()
div_term = torch.exp(torch.arange(0, d_model, 2).float() * -(math.log(10000.0) / d_model))
pe[:, 0::2] = torch.sin(position * div_term) # 偶数维
pe[:, 1::2] = torch.cos(position * div_term) # 奇数维
return pe
# RoPE 核心思想
def apply_rope(q, k, position):
"""旋转位置编码:把位置信息编码为复数旋转"""
d = q.shape[-1]
freqs = 1.0 / (10000 ** (torch.arange(0, d, 2).float() / d))
angles = position * freqs # [seq_len, d/2]
cos = angles.cos()
sin = angles.sin()
# 把 q/k 看作复数对,旋转对应角度
q_rot = torch.stack([q[..., ::2]*cos - q[..., 1::2]*sin,
q[..., ::2]*sin + q[..., 1::2]*cos], dim=-1).flatten(-2)
k_rot = torch.stack([k[..., ::2]*cos - k[..., 1::2]*sin,
k[..., ::2]*sin + k[..., 1::2]*cos], dim=-1).flatten(-2)
return q_rot, k_rot
| 算法 | 核心公式 | 使用场景 |
|---|---|---|
| BatchNorm | γ·(x-μ_B)/√(σ²_B+ε) + β | CNN(ResNet 等) |
| LayerNorm | γ·(x-μ)/√(σ²+ε) + β | Transformer、RNN |
| RMSNorm | x / √(mean(x²)+ε) · γ | Llama、现代 LLM |
| GroupNorm | 介于 BN 和 LN 之间 | 小 batch 场景 |
BatchNorm 对每个特征维度计算 batch 内的均值和方差。但序列长度可变时,不同位置的统计量不稳定。LayerNorm 对每个样本独立归一化,不依赖 batch,适合变长序列。RMSNorm 更进一步,去掉了均值中心化,只保留缩放,计算更快且效果相当。
class RMSNorm(torch.nn.Module):
"""Llama 使用的 RMSNorm"""
def __init__(self, d_model, eps=1e-6):
super().__init__()
self.weight = torch.nn.Parameter(torch.ones(d_model))
self.eps = eps
def forward(self, x):
rms = torch.sqrt(x.pow(2).mean(-1, keepdim=True) + self.eps)
return x / rms * self.weight
# LayerNorm 实现
class LayerNorm(torch.nn.Module):
def __init__(self, d_model, eps=1e-6):
super().__init__()
self.gamma = torch.nn.Parameter(torch.ones(d_model))
self.beta = torch.nn.Parameter(torch.zeros(d_model))
self.eps = eps
def forward(self, x):
mean = x.mean(-1, keepdim=True)
std = x.std(-1, keepdim=True)
return self.gamma * (x - mean) / (std + self.eps) + self.beta
# LSTM 核心公式(简化实现)
class SimpleLSTM(torch.nn.Module):
def __init__(self, input_size, hidden_size):
super().__init__()
self.hidden_size = hidden_size
# 四个门的权重合并
self.W = torch.nn.Linear(input_size + hidden_size, 4 * hidden_size)
def forward(self, x, state=None):
batch_size, seq_len, _ = x.shape
if state is None:
h = torch.zeros(batch_size, self.hidden_size, device=x.device)
c = torch.zeros(batch_size, self.hidden_size, device=x.device)
else:
h, c = state
outputs = []
for t in range(seq_len):
combined = torch.cat([x[:, t, :], h], dim=1)
gates = self.W(combined)
# 拆分四个门
i = torch.sigmoid(gates[:, :self.hidden_size]) # 输入门
f = torch.sigmoid(gates[:, self.hidden_size:2*self.hidden_size]) # 遗忘门
g = torch.tanh(gates[:, 2*self.hidden_size:3*self.hidden_size]) # 候选值
o = torch.sigmoid(gates[:, 3*self.hidden_size:]) # 输出门
c = f * c + i * g # 更新细胞状态
h = o * torch.tanh(c) # 更新隐藏状态
outputs.append(h)
return torch.stack(outputs, dim=1), (h, c)
图神经网络是处理图结构数据的深度学习模型。社交网络、分子结构、知识图谱——这些天然都是图,GNN 能直接在图上学习。
想象一个班级的社交网络。每个同学是一个节点,朋友关系是边。GNN 的做法:每个同学先听自己朋友们的意见(聚合邻居信息),然后更新自己的看法。反复几轮后,每个同学的"表示"就包含了整个朋友圈的信息。
所有 GNN 都遵循统一的消息传递范式:
GCN 是最经典的 GNN。每一层的更新公式:
import torch
import torch.nn as nn
class GCNLayer(nn.Module):
"""图卷积网络层"""
def __init__(self, in_features, out_features):
super().__init__()
self.linear = nn.Linear(in_features, out_features)
def forward(self, x, adj):
"""
x: [N, in_features] 节点特征
adj: [N, N] 邻接矩阵(已加自环)
"""
# 计算归一化邻接矩阵 D^(-1/2) A D^(-1/2)
deg = adj.sum(dim=1)
deg_inv_sqrt = deg.pow(-0.5)
deg_inv_sqrt[deg_inv_sqrt == float('inf')] = 0
norm_adj = deg_inv_sqrt.unsqueeze(1) * adj * deg_inv_sqrt.unsqueeze(0)
# 消息传递 + 线性变换
support = self.linear(x)
output = torch.matmul(norm_adj, support)
return torch.relu(output)
class GCN(nn.Module):
"""两层 GCN 用于节点分类"""
def __init__(self, in_features, hidden_features, out_features):
super().__init__()
self.conv1 = GCNLayer(in_features, hidden_features)
self.conv2 = GCNLayer(hidden_features, out_features)
def forward(self, x, adj):
x = self.conv1(x, adj)
x = self.conv2(x, adj)
return x
GraphSAGE 不用全图邻接矩阵,而是采样固定数量的邻居,适合大规模图。
class SAGELayer(nn.Module):
"""GraphSAGE 层:采样 + 聚合 + 更新"""
def __init__(self, in_features, out_features):
super().__init__()
self.linear_self = nn.Linear(in_features, out_features)
self.linear_neighbor = nn.Linear(in_features, out_features)
def forward(self, x, neighbor_indices):
"""
x: [N, in_features]
neighbor_indices: 每个节点采样的邻居索引
"""
# 聚合邻居信息(均值)
neighbor_feats = x[neighbor_indices] # [N, sample_size, in_features]
agg = neighbor_feats.mean(dim=1) # [N, in_features]
# 更新:拼接自身和邻居,线性变换
h_self = self.linear_self(x)
h_neighbor = self.linear_neighbor(agg)
return torch.relu(h_self + h_neighbor)
GAT 用注意力机制给不同邻居分配不同权重。工业实现使用 edge_index(稀疏边列表)而非密集邻接矩阵,避免 O(N²) 内存。
import torch
import torch.nn as nn
import torch.nn.functional as F
class SparseGATLayer(nn.Module):
"""稀疏 GAT:基于 edge_index 的消息传递,O(E) 而非 O(N²)"""
def __init__(self, in_features, out_features, n_heads=4):
super().__init__()
self.n_heads = n_heads
self.d_k = out_features // n_heads
self.W = nn.Linear(in_features, out_features, bias=False)
self.a_src = nn.Parameter(torch.randn(n_heads, self.d_k))
self.a_dst = nn.Parameter(torch.randn(n_heads, self.d_k))
self.leaky_relu = nn.LeakyReLU(0.2)
def forward(self, x, edge_index):
"""
x: [N, in_features] 节点特征
edge_index: [2, E] 边列表(src, dst)
"""
N = x.shape[0]
src, dst = edge_index # src[e] -> dst[e]
# 线性投影 + 分头
h = self.W(x).view(N, self.n_heads, self.d_k) # [N, heads, d_k]
# 计算每条边的注意力分数(只算存在的边,O(E))
e_src = (h[src] * self.a_src).sum(dim=-1) # [E, heads]
e_dst = (h[dst] * self.a_dst).sum(dim=-1) # [E, heads]
e = self.leaky_relu(e_src + e_dst) # [E, heads]
# Softmax 归一化(按目标节点分组)
# 用 scatter 实现分组 softmax
alpha = torch.zeros_like(e)
for head in range(self.n_heads):
e_h = e[:, head]
# 每个目标节点的入边 softmax
exp_e = torch.exp(e_h - e_h.max())
denom = torch.zeros(N, device=x.device)
denom.scatter_add_(0, dst, exp_e)
alpha[:, head] = exp_e / (denom[dst] + 1e-9)
# 消息传递:加权聚合邻居特征(O(E))
msg = h[src] * alpha.unsqueeze(-1) # [E, heads, d_k]
out = torch.zeros(N, self.n_heads, self.d_k, device=x.device)
out.scatter_add_(0, dst.unsqueeze(-1).unsqueeze(-1).expand_as(msg), msg)
return out.reshape(N, -1)
# 示例:PyG 风格的使用方式
edge_index = torch.tensor([[0,1,1,2,3,0], [1,0,2,1,0,3]]) # 4 条无向边
x = torch.randn(4, 16) # 4 个节点,16 维特征
gat = SparseGATLayer(16, 32, n_heads=4)
out = gat(x, edge_index)
print(f"输入: {x.shape} → 输出: {out.shape}") # [4,16] → [4,32]
实际项目中直接用 PyTorch Geometric (PyG),它提供了 MessagePassing 基类和自动稀疏消息传递:
# PyG 工业级写法(需安装 torch_geometric)
from torch_geometric.nn import MessagePassing, GATConv, GCNConv
# 方式 1:直接用内置层
class GNN(nn.Module):
def __init__(self, in_dim, hidden_dim, out_dim):
super().__init__()
self.conv1 = GCNConv(in_dim, hidden_dim)
self.conv2 = GATConv(hidden_dim, hidden_dim, heads=4)
self.conv3 = GCNConv(hidden_dim * 4, out_dim)
def forward(self, x, edge_index):
x = F.relu(self.conv1(x, edge_index))
x = F.relu(self.conv2(x, edge_index))
return self.conv3(x, edge_index)
# 方式 2:自定义消息传递层
class MyConv(MessagePassing):
def __init__(self, in_dim, out_dim):
super().__init__(aggr='mean') # 聚合方式:mean/sum/max
self.lin = nn.Linear(in_dim, out_dim)
def forward(self, x, edge_index):
return self.propagate(edge_index, x=self.lin(x))
def message(self, x_j):
"""x_j: [E, out_dim] 邻居的消息"""
return x_j # 可以加注意力权重
# 使用 PyG 的 Data 对象
from torch_geometric.data import Data
data = Data(x=x, edge_index=edge_index)
# DataLoader 自动处理 batch
from torch_geometric.loader import DataLoader
本章是全书的"工具箱"——当你遇到问题时,快速查到该用什么算法、什么复杂度、怎么实现。
| 数据结构 / 算法 | 查找 | 插入 | 删除 | 空间 |
|---|---|---|---|---|
| 数组 | O(1) 按下标 | O(n) | O(n) | O(n) |
| 链表 | O(n) | O(1) | O(1) | O(n) |
| 哈希表 | O(1) 平均 | O(1) 平均 | O(1) 平均 | O(n) |
| 二叉搜索树 | O(log n) | O(log n) | O(log n) | O(n) |
| 堆 | O(n) 查找 | O(log n) | O(log n) | O(n) |
| 跳表 | O(log n) | O(log n) | O(log n) | O(n log n) |
| 算法 | 平均 | 最坏 | 空间 | 稳定 | 适用场景 |
|---|---|---|---|---|---|
| Timsort | O(n log n) | O(n log n) | O(n) | ✅ | Python sorted(),通用 |
| 快排 | O(n log n) | O(n²) | O(log n) | ❌ | 内存敏感场景 |
| 归并 | O(n log n) | O(n log n) | O(n) | ✅ | 链表排序,外部排序 |
| 计数/基数 | O(n+k) | O(n+k) | O(k) | ✅ | 整数/字符串排序 |
| 问题 | 算法 | PyTorch / 库 |
|---|---|---|
| Top-K 采样 | 最小堆 | torch.topk() |
| Softmax | 指数归一化 | F.softmax() |
| 注意力 | Scaled Dot-Product | nn.MultiheadAttention() |
| 最近邻 | HNSW | faiss.IndexHNSWFlat() |
| 模型微调 | LoRA | peft.LoraConfig() |
| 模型量化 | GPTQ/AWQ | auto-gptq / autoawq |
| 分布式训练 | DDP/ZeRO | torch.nn.parallel.DistributedDataParallel |
| 优化器 | AdamW | torch.optim.AdamW() |
| 学习率调度 | Cosine Decay | CosineAnnealingLR |
| 模型推理 | KV Cache | vllm / text-generation-inference |
torch.nn.utils.clip_grad_norm_ 裁剪。❌ Adam 的 β₂ 设成 0.99(默认 0.999)→ 学习率过早衰减,欠拟合。保持默认。
❌ 微调大模型时学习率设 0.01 → 破坏预训练知识。用 1e-5 ~ 5e-5。
❌ 不同层用相同学习率 → 底层变化太大。用 Layer-wise LR Decay。
❌ 忘记 shuffle 训练数据 → 模型学到顺序偏差。
❌ 测试集泄露到训练集 → 指标虚高,上线崩盘。
❌ 类别不平衡不做处理 → 模型偏向多数类。用过采样 / 欠采样 / Focal Loss。
❌ 量化后不测精度 → 可能精度暴跌。量化后必须在验证集上测。
❌ 不做 batch 推理 → GPU 利用率极低。用连续批处理。
❌ 忘记设置 eval 模式 → Dropout 和 BatchNorm 行为不对。