术语表

按主题分组的中英对照速查；详细机制见对应知识点。

按主题分组，中文名在前，首次出现附英文原词。解释保持一句话，细节见对应知识点。

基础与分析

术语	英文	一句话解释
算法	Algorithm	求解特定问题的有限、明确、可终止的步骤序列。
数据结构	Data Structure	组织与存储数据以支持一组高效操作的方式。
抽象数据类型	Abstract Data Type (ADT)	只规定操作与语义约定、不规定实现的逻辑接口。
不变量	Invariant	在操作前后必须保持成立的性质，是正确性证明的锚点。
时间复杂度	Time Complexity	运行时间随输入规模增长的增长阶刻画。
空间复杂度	Space Complexity	额外辅助空间随输入规模增长的增长阶。
大 O 记号	Big-O Notation	给出增长阶上界的渐进记号，对应地还有 Ω 与 Θ。
均摊分析	Amortized Analysis	把偶发昂贵操作的代价摊到整个操作序列上的平均上界。
期望复杂度	Expected Complexity	在随机性假设下代价的数学期望，区别于最坏情形。
主定理	Master Theorem	直接求解 T(n)=aT(n/b)+f(n) 型递归式的定理。
NP 完全	NP-Complete	一类「只要其中一个有多项式算法则全体都有」的判定问题类。

数据结构

术语	英文	一句话解释
动态数组	Dynamic Array	尾部追加、满了倍增搬家的连续数组，如 vector、Python list。
链表	Linked List	用指针串联节点的链式存储，牺牲随机访问换已知位置 O(1) 插删。
哨兵节点	Sentinel / Dummy Node	永远存在的头（尾）占位节点，用于消除边界特判。
栈	Stack	后进先出（LIFO）的受限线性表。
队列	Queue	先进先出（FIFO）的受限线性表。
单调栈	Monotonic Stack	保持栈内元素单调以 O(n) 求「下一个更大元素」类问题的栈。
散列函数	Hash Function	把键映射到桶下标的函数，要求确定性与均匀性。
负载因子	Load Factor	元素数 n 与桶数 m 之比 α，决定冲突概率与扩容时机。
开放寻址	Open Addressing	冲突后按探测序列在同数组内找空位的冲突策略。
布隆过滤器	Bloom Filter	位数组加多哈希实现的「可能存在/一定不存在」概率结构。
一致性哈希	Consistent Hashing	环形哈希空间加虚拟节点，使节点增减只迁移邻近数据。
二叉搜索树	Binary Search Tree (BST)	满足左子树小于根、右子树大于根的有序二叉树。
平衡因子	Balance Factor	AVL 树中节点左右子树高度之差，绝对值不超过 1。
旋转	Rotation	保持 BST 序不变、改变局部高度的重组操作。
堆	Heap	满足堆序性质（父不大于/不小于子）的完全二叉树。
优先队列	Priority Queue	每次取最值的 ADT，典型实现是堆。
B+ 树	B+ Tree	面向块存储的多路平衡树，数据全在叶子并以链表相连。
LSM 树	Log-Structured Merge Tree	把随机写转为顺序写、靠分层合并维护读性能的存储引擎骨架。
图	Graph	顶点与边的集合 G=(V,E)，分有向/无向、带权/无权。
邻接表	Adjacency List	每个顶点挂一个邻居列表的图表示，适合稀疏图。
广度优先搜索	Breadth-First Search (BFS)	按层扩展的图遍历，队列实现，可求无权最短路。
深度优先搜索	Depth-First Search (DFS)	一条路走到黑再回溯的图遍历，栈或递归实现。
松弛	Relaxation	若经中转点路径更短则更新距离估计的基本操作。
最小生成树	Minimum Spanning Tree (MST)	连通所有顶点且边权和最小的无环边集。
拓扑排序	Topological Sort	DAG 顶点的线性序，保证每条边从前指向后。
强连通分量	Strongly Connected Component (SCC)	有向图中互相可达的极大顶点集。
并查集	Union-Find / Disjoint Set	支持合并与查询所属集合的结构，两优化后近 O(1)。
路径压缩	Path Compression	find 时把沿途节点直接挂到根上的优化。
位掩码	Bitmask	用整数的二进制位表示集合以加速集合运算。
前缀函数	Prefix Function (failure/next)	模式串每个前缀的最长相等真前后缀长度，KMP 的核心。

算法思想与工程

术语	英文	一句话解释
分治	Divide and Conquer	分解、独立求解、合并三步的通用设计框架。
贪心	Greedy	每步取局部最优，成立需贪心选择性质与交换论证。
动态规划	Dynamic Programming (DP)	利用重叠子问题与最优子结构，以状态与转移避免重复计算。
记忆化	Memoization	缓存子问题结果的 DP 自顶向下形态。
回溯	Backtracking	系统枚举解空间的 DFS，配合剪枝砍掉无效分支。
剪枝	Pruning	提前判定子树不可能产生答案从而整支跳过。
状态压缩 DP	Bitmask DP	以位掩码表示已访问集合的动态规划。
稳定性	Stability (sorting)	相等键排序后相对次序保持不变的排序性质。
原地	In-place	只用 O(1) 或 O(log n) 额外空间完成排序。
决策树	Decision Tree	把比较排序过程建模为二叉树以证 n log n 下界的模型。
对拍	Differential Testing	暴力解与优化解在随机数据上互相比对以验证正确性的方法。
算法公平性	Algorithmic Fairness	算法决策对不同群体不产生系统性不公正对待的要求。

说明：本清单基于模型知识整理，均为真实存在的经典著作、论文与课程，未附链接；建议按需核对原文与最新版本。

书籍

《算法导论》（Introduction to Algorithms），Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest、Clifford Stein —— 理论体系最全的参考书，复杂度分析、图算法、字符串章节可作深读材料。
《算法（第 4 版）》（Algorithms, 4th Edition），Robert Sedgewick、Kevin Wayne —— 配合 Java 实现讲解，工程视角友好。
《计算机程序设计艺术》（The Art of Computer Programming），Donald E. Knuth —— 算法学科的奠基性著作，本库 kp-005 的主线索。
《算法设计》（Algorithm Design），Jon Kleinberg、Éva Tardos —— 算法设计思想（贪心、分治、DP、网络流）讲得最透。
《数据结构与算法分析：C 语言描述》（Data Structures and Algorithm Analysis in C），Mark Allen Weiss —— 结构实现细节与均摊分析的好教材。
《编程珠玑》（Programming Pearls），Jon Bentley —— 工程实践与问题建模的经典，对应 kp-032。
《算法设计指南》（The Algorithm Design Manual），Steven S. Skiena —— 以「问题—解法」目录组织，适合按场景查阅。
《算法竞赛入门经典》，刘汝佳 —— 竞赛视角的紧凑讲义，适合训练路线设计。

论文

E. W. Dijkstra, "A Note on Two Problems in Connexion with Graphs"（1959）—— 最短路问题的原始论文。
J. B. Kruskal, "On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem"（1956）。
R. C. Prim, "Shortest Connection Networks and Some Generalizations"（1957）。
R. E. Tarjan, "Efficiency of a Good But Not Linear Set Union Algorithm"（1975）—— 并查集逆阿克曼复杂度分析。
D. E. Knuth, J. H. Morris, V. R. Pratt, "Fast Pattern Matching in Strings"（1977）—— KMP 算法。
P. O'Neil 等, "The Log-Structured Merge-Tree (LSM-Tree)"（1996）—— LSM 存储引擎的源头。
J. L. Bentley, M. D. McIlroy, "Engineering a Sort Function"（1993）—— 工业级排序函数的设计与坑。

课程与延伸

MIT 6.006 Introduction to Algorithms（公开课）—— 与本库模块划分高度对应，可作为视频补充。
《算法霸权：大数据杀伤性武器与威胁》（Weapons of Math Destruction），Cathy O'Neil —— 算法伦理与公平性的大众读物，对应 kp-033。
Fairness and Machine Learning: Limitations and Opportunities，Solon Barocas、Moritz Hardt、Arvind Narayanan —— 公平性度量的系统教材。