Ch14 数据结构与算法 · 闪卡 (Anki 导出)¶

100 张卡,涵盖 6 节核心。Anki Deck: Ch14 数据结构与算法

Section A: 基础¶

Card 1¶

Front: 大 O 记号定义? Back: \(T(n) = O(f(n))\) 当 \(\exists c > 0, n_0: T(n) \leq c f(n), \forall n \geq n_0\)。

Card 2¶

Front: 主定理? Back: \(T(n) = a T(n/b) + f(n)\), 分三情况与 \(n^{\log_b a}\) 比较。

Card 3¶

Front: 递归三要素? Back: (1) 基例 (终止条件), (2) 递归调用 (规模缩小), (3) 返回组合。

Card 4¶

Front: 分治 vs 动态规划? Back: 分治: 子问题独立; DP: 子问题重叠, 用记忆化。

Card 5¶

Front: 平摊分析 (amortized)? Back: 单次操作平均成本。e.g., 动态数组扩容 \(O(1)\) 平摊。

Card 6¶

Front: 时间换空间经典例子? Back: 哈希表 (\(O(n)\) 空间换 \(O(1)\) 查找), DP 表 (\(O(n^2)\) 换 \(O(1)\) 查询)。

Card 7¶

Front: 空间换时间例子? Back: 记忆化递归 (memoization), 索引 (database)。

Card 8¶

Front: 尾递归优化? Back: 递归调用是函数最后操作, 编译器复用栈帧。Python 不支持。

Card 9¶

Front: 迭代 vs 递归? Back: 递归简洁, 但栈 \(O(n)\); 迭代空间 \(O(1)\) 但代码长。

Card 10¶

Front: 大 O 常见复杂度排序? Back: \(O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(2^n) < O(n!)\)。

Section B: 数组与哈希¶

Card 11¶

Front: 数组随机访问复杂度? Back: \(O(1)\)。CPU 直接计算偏移。

Card 12¶

Front: 动态数组插入均摊? Back: 末尾插入 \(O(1)\) 平摊 (偶尔扩容 \(O(n)\)), 中间插入 \(O(n)\)。

Card 13¶

Front: 哈希表平均查找复杂度? Back: \(O(1)\)。最坏 \(O(n)\) (冲突)。

Card 14¶

Front: 哈希冲突解决方法? Back: (1) 链地址 (chaining), (2) 开放定址 (probing, e.g., 线性/二次/双重哈希)。

Card 15¶

Front: 装填因子? Back: \(\alpha = n/m\), \(n\) 元素数, \(m\) 桶数。> 0.7 通常扩容。

Card 16¶

Front: 一致性哈希? Back: 节点 / 数据映射到 0-2^32 环。增删节点只影响邻居, 用于分布式缓存。

Card 17¶

Front: 双指针算法适用场景? Back: 有序数组查找, 链表快慢指针, 字符串匹配。

Card 18¶

Front: 滑动窗口适用? Back: 数组 / 字符串子串问题, 求最长 / 最短满足条件子串。

Card 19¶

Front: 前缀和适用? Back: 区间求和 \(O(1)\) 查询, 多次询问。

Card 20¶

Front: Python list 是数组还是链表? Back: 动态数组 (C 实现), 不是链表。中间插入 \(O(n)\)。

Section C: 链表栈队¶

Card 21¶

Front: 链表 vs 数组核心差别? Back: 数组连续内存访问 \(O(1)\), 链表非连续访问 \(O(n)\); 数组插入 \(O(n)\), 链表 \(O(1)\)。

Card 22¶

Front: 单链表反转核心代码? Back:

prev, curr = None, head
while curr:
    nxt = curr.next
    curr.next = prev
    prev = curr
    curr = nxt
return prev

Card 23¶

Front: 快慢指针应用? Back: 链表环检测 (Floyd), 找中点, 找倒数第 k。

Card 24¶

Front: LRU Cache 实现? Back: 双向链表 + 哈希表。访问移到头, 淘汰尾。

Card 25¶

Front: 单调栈应用? Back: 下一个更大元素, 接雨水, 柱状图最大矩形。

Card 26¶

Front: 队列应用? Back: BFS, 任务调度, 滑动窗口, 消息队列 (Kafka)。

Card 27¶

Front: 优先队列底层? Back: 二叉堆 (heap)。Python heapq 是最小堆。

Card 28¶

Front: 双端队列 (deque)? Back: 两端插入删除 \(O(1)\)。Python collections.deque。

Card 29¶

Front: 循环队列? Back: 用数组 + head/tail 指针实现队列, 节省空间。

Card 30¶

Front: 表达式求值用栈还是队列? Back: 栈 (中缀 → 后缀 → 求值)。

Section D: 树¶

Card 31¶

Front: 二叉树前序遍历? Back: 根 → 左 → 右。preorder(node): if node: print(node.val); preorder(node.left); preorder(node.right)。

Card 32¶

Front: 中序遍历 BST 结果? Back: 有序序列。

Card 33¶

Front: 层序遍历用什么数据结构? Back: 队列 (BFS)。

Card 34¶

Front: BST 查找复杂度? Back: 平均 \(O(\log n)\), 最坏 \(O(n)\) (退化成链表)。

Card 35¶

Front: AVL 树 vs 红黑树? Back: AVL 严格平衡 (高度差 ≤ 1), 查找快; 红黑树近似平衡 (黑高一致), 插入删除快。

Card 36¶

Front: 堆的插入复杂度? Back: \(O(\log n)\)。先放末尾, 上浮。

Card 33¶

Front: Heapify 一次建堆复杂度? Back: \(O(n)\)。从最后一个非叶节点下调。

Card 38¶

Front: Trie (前缀树) 应用? Back: 自动补全, 拼写检查, IP 路由。

Card 39¶

Front: 树状数组 (BIT) 用途? Back: 区间求和 / 更新 \(O(\log n)\)。比线段树简单。

Card 40¶

Front: 线段树用途? Back: 区间查询 / 更新 \(O(\log n)\), 支持多种聚合 (min/max/sum)。

Section E: 图¶

Card 41¶

Front: BFS 时间复杂度? Back: \(O(V + E)\)。队列实现。

Card 42¶

Front: DFS 时间复杂度? Back: \(O(V + E)\)。栈 / 递归实现。

Card 43¶

Front: Dijkstra 不适用什么图? Back: 有负权边的图。负权用 Bellman-Ford。

Card 44¶

Front: 拓扑排序前提? Back: DAG (有向无环图)。Kahn 算法或 DFS 后序逆序。

Card 45¶

Front: Bellman-Ford 复杂度? Back: \(O(VE)\)。可检测负权环。

Card 46¶

Front: Floyd-Warshall 复杂度? Back: \(O(V^3)\)。所有点对最短路。

Card 47¶

Front: Prim vs Kruskal? Back: Prim 适合稠密图 (\(O(V^2)\) 或 \(O(E \log V)\)), Kruskal 适合稀疏图 (\(O(E \log E)\), 用 Union-Find)。

Card 48¶

Front: Union-Find 优化? Back: 路径压缩 + 按秩合并 → 几乎 \(O(1)\)。

Card 49¶

Front: A 启发式函数要求? Back*: \(h(n) \leq \text{真实代价}\), 可采纳 (admissible)。否则不能保证最优。

Card 50¶

Front: 强连通分量 (SCC)? Back: 任意两节点互相可达的最大子图。Tarjan / Kosaraju 算法 \(O(V+E)\)。

Section F: 排序¶

Card 51¶

Front: 常见排序稳定性? Back: 稳定: 冒泡 / 插入 / 归并 / 计数 / Tim。不稳定: 选择 / 快排 / 堆排 / 希尔。

Card 52¶

Front: 快速排序最坏情况? Back: \(O(n^2)\) (每次选最大 / 最小为 pivot)。随机化 pivot 可避免。

Card 53¶

Front: 归并排序空间复杂度? Back: \(O(n)\)。需要辅助数组。

Card 54¶

Front: 堆排序空间? Back: \(O(1)\) 原地。

Card 55¶

Front: 计数排序适用? Back: 数据范围 \(k\) 较小, e.g., 0-100 的分数排序。\(O(n+k)\)。

Card 56¶

Front: 基数排序适用? Back: 定长整数 / 字符串。按位排序, \(O(nk)\)。

Card 57¶

Front: Tim 排序 (Python sort)? Back: 归并 + 插入, 自适应。识别已有有序片段 (run), 合并。最坏 \(O(n \log n)\)。

Card 58¶

Front: 二分查找前提? Back: 有序数组。

Card 59¶

Front: 二分查找边界 (左闭右闭)? Back:

lo, hi = 0, n - 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

Card 60¶

Front: 二分查找变种 (找左边界)? Back:

lo, hi = 0, n
while lo < hi:
    mid = (lo + hi) // 2
    if arr[mid] < target: lo = mid + 1
    else: hi = mid
return lo

Section G: 现实应用¶

Card 61¶

Front: LLM 推理中 KV cache 用什么数据结构? Back: 哈希表 + 张量。vLLM PagedAttention 用 page table 类似 OS。

Card 62¶

Front: GNN 邻居采样用什么? Back: BFS (GraphSAINT), kNN (点云), 邻接表遍历。

Card 63¶

Front: 数据库索引底层? Back: B+ 树 (InnoDB), LSM 树 (LevelDB / RocksDB)。

Card 64¶

Front: 推荐系统 Top-K? Back: 堆 (heap), \(O(n \log k)\)。

Card 65¶

Front: PageRank 实现? Back: 邻接表 + 迭代幂法。GPU 上用 sparse mat-vec。

Card 66¶

Front: SLAM 路径规划? Back: Dijkstra / A* 在栅格图。

Card 67¶

Front: 编译器符号表? Back: 哈希表 (Python), 红黑树 (C++)。

Card 68¶

Front: Trie 在 LLM 应用? Back: BPE tokenizer 的 prefix cache, Beam search 缓存。

Card 69¶

Front: 数据库连接用什么算法? Back: Hash Join (等值), Sort-Merge Join (范围)。

Card 70¶

Front: 内存池用什么数据结构? Back: 双向链表 (空闲块), 哈希表 (按大小索引)。

Section H: 历史¶

Card 71¶

Front: Quick Sort 起源? Back: Tony Hoare, 1960。

Card 72¶

Front: Heap Sort 起源? Back: Williams / Floyd, 1964。

Card 73¶

Front: Dijkstra 起源? Back: Edsger Dijkstra, 1956 (设计), 1959 出版。

Card 74¶

Front: AVL 树起源? Back: Adelson-Velsky & Landis, 1962, 第一个自平衡树。

Card 75¶

Front: 红黑树起源? Back: Rudolf Bayer, 1972。

Card 76¶

Front: B+ 树起源? Back: Rudolf Bayer, 1972, 用于数据库索引。

Card 77¶

Front: Tarjan SCC 起源? Back: Robert Tarjan, 1972。

Card 78¶

Front: Tim 排序起源? Back: Tim Peters, 2002, Python 标准。

Card 79¶

Front: MapReduce 起源? Back: Google, Dean & Ghemawat, OSDI 2004。

Card 80¶

Front: PagedAttention 起源? Back: vLLM, Kwon et al., SOSP 2023。

Section I: 工程¶

Card 81¶

Front: Python list vs tuple? Back: list 可变, tuple 不可变 (哈希)。tuple 快 ~10%。

Card 82¶

Front: Python dict 实现? Back: 开放定址哈希表, 装填因子 2/3。Python 3.7+ 保插入序。

Card 83¶

Front: Python set 实现? Back: 同 dict, 但只存 key。

Card 84¶

Front: Python deque vs list? Back: deque 两端 \(O(1)\), list 末端 \(O(1)\), 头部 \(O(n)\)。

Card 85¶

Front: C++ STL vector 扩容策略? Back: 1.5× 或 2× 扩容。Java ArrayList 1.5×, Python list 1.125×。

Card 86¶

Front: Rust Vec 扩容? Back: 2× 扩容, \(O(1)\) 平摊。

Card 87¶

Front: C++ std::unordered_map vs std::map? Back: 前者哈希 \(O(1)\), 后者红黑 \(O(\log n)\), 后者有序。

Card 88¶

Front: 为什么 hash 函数要均匀? Back: 否则聚集 → 冲突 → 退化 \(O(n)\)。

Card 89¶

Front: 数据库 B+ 树为什么不用红黑? Back: B+ 树磁盘友好 (节点大, IO 少), 红黑树是内存结构。

Card 90¶

Front: LSM 树优势? Back: 写优化 (顺序 IO), 用于 KV 存储 (LevelDB, RocksDB)。

Section J: 跨章¶

Card 91¶

Front: Ch07 §04 Transformer 与 Ch14 §03 Trie 的关系? Back: BPE tokenizer 是 Trie 变种, 前缀匹配。

Card 92¶

Front: Ch12 §02 GNN 与 Ch14 §04 图算法的关系? Back: GNN 邻居采样 = BFS/DFS, GraphSAINT 用 Dijkstra/Union-Find。

Card 93¶

Front: Ch11 §05 SLAM 与 Ch14 §04 Dijkstra? Back: SLAM 回环检测用图, A* 用于路径规划。

Card 94¶

Front: Ch13 §03 虚拟内存与 Ch14 §02 LRU? Back: OS 页置换算法 = LRU 变种。

Card 95¶

Front: Ch05 §04 贝叶斯与 Ch14 §03 Trie? Back: 前缀概率 = Trie + 条件概率。

Card 96¶

Front: Ch08 §04 Diffusion 与 Ch14 §03 KD-Tree? Back: k-NN 去噪用 KD-Tree 找邻居。

Card 97¶

Front: Ch06 §04 RL 与 Ch14 §03 堆? Back: 优先级经验回放用堆 (PER)。

Card 98¶

Front: Ch03 §05 梯度与 Ch14 §05 排序? Back: 分布式 Shuffle 用排序。

Card 99¶

Front: Ch13 §04 并发与 Ch14 §03 优先队列? Back: 多线程任务调度用优先队列 (lock-free heap)。

Card 100¶

Front: 一句话总结 Ch14。 Back: 数据结构与算法 = AI 工程师内功。覆盖 §00 基础 (复杂度/递归) + §01 数组哈希 (\(O(1)\) 访问/查找) + §02 链表栈队 (LRU / 队列) + §03 树 (BST / 平衡 / Trie / 堆) + §04 图 (BFS / DFS / Dijkstra / MST) + §05 排序搜索 (快排 / 归并 / Tim / 二分)。是 GNN/SLAM/LLM 推理优化的基础。