Appearance
附录 C · 术语中英对照表
按章组织，便于回看正文时检索；同时给出常见英文缩写与易混术语辨析。
一、第 2 章 初等数论
| 中文 | 英文 | 说明 |
|---|---|---|
| 素数 / 质数 | prime (number) | 大于 1 且只有 1 和自身两个因数 |
| 合数 | composite (number) | 大于 1 且除 1、自身外还有其他因数 |
| 因数 / 约数 | divisor / factor | 能整除给定整数的数 |
| 倍数 | multiple | — |
| 最大公约数 | GCD, Greatest Common Divisor | 也写作 HCF |
| 最小公倍数 | LCM, Least Common Multiple | — |
| 辗转相除法 / 欧几里得算法 | Euclidean algorithm | gcd(a,b) = gcd(b, a%b) |
| 同余 | congruence | a ≡ b (mod m) |
| 模运算 | modular arithmetic | 加减乘可分布取模，除法不行 |
| 逆元 | modular inverse | 五级不要求 |
| 唯一分解定理 / 算术基本定理 | Fundamental Theorem of Arithmetic | 每个大于 1 的整数可唯一表示为素数乘积 |
| 质因数分解 | prime factorization | — |
| 指数（分解式中的） | exponent | 如 2³ 中的 3 |
| 埃氏筛法 | Sieve of Eratosthenes | O(n log log n) |
| 线性筛法 / 欧拉筛 | Euler's sieve / Linear sieve | O(n) |
| 最小质因子 | smallest prime factor | 线性筛的筛除依据 |
| 奇偶性 | parity | 奇数 odd / 偶数 even |
| 快速幂 | fast exponentiation / binary exponentiation | 反复平方法，O(log n)（超纲） |
二、第 3 章 链表
| 中文 | 英文 | 说明 |
|---|---|---|
| 链表 | linked list | 离散内存 + 指针串联 |
| 节点 | node | 数据域 + 指针域 |
| 数据域 | data field | 存放元素值 |
| 指针域 | pointer field | 存放后继/前驱地址 |
| 头节点 / 头指针 | head (node) | 链表入口 |
| 尾节点 | tail (node) | — |
| 前驱 / 后继 | predecessor / successor | — |
| 单链表 | singly linked list | 只有 next |
| 双链表 | doubly linked list | prev + next |
| 循环链表 | circular linked list | 尾节点指向头节点 |
| 头插法 / 尾插法 | insert at head / insert at tail | — |
| 反转 | reverse | 三指针法 |
| 遍历 | traverse | — |
| 空指针 | null pointer | C++ 写 nullptr |
| 野指针 | dangling pointer | 指向已释放内存 |
| 内存泄漏 | memory leak | new 后未 delete |
| 约瑟夫问题 | Josephus problem | 循环链表经典应用 |
三、第 4 章 高精度运算
| 中文 | 英文 | 说明 |
|---|---|---|
| 高精度运算 | big integer arithmetic / arbitrary precision | 数组模拟大整数 |
| 高精度加法 | big integer addition | — |
| 高精度减法 | big integer subtraction | — |
| 高精度乘法 | big integer multiplication | — |
| 高精度除法 | big integer division | 五级只要求 ÷ 低精度 |
| 进位 | carry | 加法/乘法 |
| 借位 | borrow | 减法 |
| 倒序存储 | reversed storage | 个位存下标 0 |
| 前导零 | leading zeros | 减法、除法需去除 |
| 试商 | trial division（逐位） | 除法逐位确定商 |
| 余数 | remainder | — |
| 溢出 | overflow | 超出类型表示范围 |
四、第 5 章 二分算法
| 中文 | 英文 | 说明 |
|---|---|---|
| 二分查找 | binary search | 前提：有序 |
| 二分答案 / 二分枚举法 | binary search on answer | 二分猜答案 + check 验证 |
| 左闭右闭区间 | closed interval [l, r] | — |
| 左闭右开区间 | half-open interval [l, r) | — |
| 中点 | midpoint | mid |
| 下界 / 上界 | lower bound / upper bound | 第一个 ≥ / 第一个 > |
| 单调性 | monotonicity | 二分答案的前提 |
| 可行性检查函数 | check function / feasibility test | 返回 bool |
| 向下取整 / 向上取整 | floor / ceiling | — |
| 死循环 | infinite loop | 区间不缩小导致 |
| 精度 | precision / epsilon | 浮点二分终止条件 |
五、第 6 章 递归
| 中文 | 英文 | 说明 |
|---|---|---|
| 递归 | recursion | 函数调用自身 |
| 基线条件 | base case | 递归出口 |
| 递归条件 | recursive case | — |
| 调用栈 | call stack | — |
| 栈帧 | stack frame | 参数 + 局部变量 + 返回地址 |
| 压栈 / 出栈 | push / pop | — |
| 递归深度 | recursion depth | = 栈空间复杂度 |
| 栈溢出 | stack overflow | 深度过大导致 |
| 递归树 | recursion tree | 分析复杂度用 |
| 记忆化搜索 | memoization | 自顶向下的 DP |
| 重复子问题 | overlapping subproblems | 记忆化的适用条件 |
| 回溯 | backtracking | 选择 → 递归 → 撤销 |
| 全排列 | permutation | — |
| 汉诺塔 | Tower of Hanoi | 2ⁿ-1 步 |
| 迭代 | iteration | 自底向上 |
六、第 7 章 分治算法
| 中文 | 英文 | 说明 |
|---|---|---|
| 分治 | divide and conquer | 分解 → 解决 → 合并 |
| 归并排序 | merge sort | O(n log n)，稳定 |
| 快速排序 | quick sort | 平均 O(n log n)，不稳定 |
| 基准元素 | pivot | — |
| 分区 | partition | — |
| 合并 | merge | 双指针合并两个有序数组 |
| 逆序对 | inversion (pair) | i<j 且 a[i]>a[j] |
| 稳定性 | stability | 相等元素相对顺序不变 |
| 原地排序 | in-place sort | 辅助空间 O(1) |
| 快速选择 | quick select | 第 k 大/小（超纲） |
| 最大子段和 | maximum subarray sum | 分治三种情况 |
| 主定理 | Master Theorem | 递归式求解（超纲） |
七、第 8 章 贪心算法
| 中文 | 英文 | 说明 |
|---|---|---|
| 贪心算法 | greedy algorithm | 每步选局部最优 |
| 贪心选择性质 | greedy choice property | — |
| 最优子结构 | optimal substructure | 贪心与 DP 的共同要求 |
| 动态规划 | dynamic programming (DP) | 枚举所有选择取最优 |
| 活动选择 / 区间调度 | activity selection / interval scheduling | 按结束时间排序 |
| 区间覆盖 | interval covering | 按左端点排序，选最远右端点 |
| 区间选点 | interval point selection | 按右端点排序 |
| 哈夫曼（树/编码） | Huffman (tree / coding) | 合并果子即哈夫曼构造 |
| 优先队列 | priority queue | STL priority_queue（超纲） |
| 小根堆 / 大根堆 | min-heap / max-heap | — |
| 交换论证 | exchange argument | 贪心正确性证明法 |
| 反证法 | proof by contradiction | — |
| 规范货币系统 | canonical coin system | 贪心找零成立的条件 |
| 排队接水 | queue for water | 短作业优先 |
| 乘船问题 | boat problem | 最轻 + 最重双指针 |
八、第 9 章 算法复杂度分析
| 中文 | 英文 | 说明 |
|---|---|---|
| 时间复杂度 | time complexity | — |
| 空间复杂度 | space complexity | — |
| 大 O 表示法 | Big-O notation | 渐进上界 |
| 渐进分析 | asymptotic analysis | — |
| 常数复杂度 | constant, O(1) | — |
| 对数复杂度 | logarithmic, O(log n) | 折半/倍增 |
| 线性复杂度 | linear, O(n) | — |
| 线性对数复杂度 | linearithmic, O(n log n) | — |
| 多项式复杂度 | polynomial, O(nᵏ) | — |
| 指数复杂度 | exponential, O(2ⁿ) | — |
| 阶乘复杂度 | factorial, O(n!) | — |
| 最好 / 最坏 / 平均情况 | best / worst / average case | 大 O 默认最坏 |
| 辅助空间 | auxiliary space | 不计输入本身 |
| 原地算法 | in-place algorithm | 辅助空间 O(1) |
| 时空权衡 | time-space tradeoff | 用空间换时间 |
| 前缀和 | prefix sum | 区间查询 O(1) |
| 哈希表 | hash table | 平均 O(1) 查找 |
| 调和级数 | harmonic series | ≈ ln n |
九、常用英文缩写速查
| 缩写 | 全称 | 中文 |
|---|---|---|
| GCD | Greatest Common Divisor | 最大公约数 |
| LCM | Least Common Multiple | 最小公倍数 |
| DP | Dynamic Programming | 动态规划 |
| DFS | Depth-First Search | 深度优先搜索 |
| BFS | Breadth-First Search | 广度优先搜索 |
| STL | Standard Template Library | C++ 标准模板库 |
| OOP | Object-Oriented Programming | 面向对象编程 |
| TLE | Time Limit Exceeded | 超时 |
| MLE | Memory Limit Exceeded | 超内存 |
| AC | Accepted | 通过 |
十、易混术语辨析
| 易混组 | 区别 |
|---|---|
| 递归 vs 分治 | 递归是编程技巧（函数调自身）；分治是算法思想（分解-解决-合并）。递归求阶乘不是分治 |
| 分治 vs 动态规划 | 分治要求子问题相互独立；DP 处理重叠子问题 |
| 贪心 vs 动态规划 | 贪心每步选当前最优不回头；DP 枚举所有选择取最优。贪心多一个"贪心选择性质"要求 |
| 稳定性 vs 正确性 | 稳定性只关注相等元素相对顺序；与排序是否正确、数据是否丢失无关 |
| 时间复杂度 vs 空间复杂度 | 前者随 n 增长的运行时间上界；后者是辅助空间上界（不计输入） |
| 递归深度 vs 递归节点数 | 空间复杂度取决于最大深度（同一时刻栈上只有一条路径），不是节点总数 |
| lower_bound vs upper_bound | 第一个 ≥ target vs 第一个 > target；只差一个等号 |
| 倒序存储 vs 正序存储 | 加减乘倒序（个位在 0）；除法正序（从高位算） |
| 头插法 vs 尾插法 | 头插 O(1) 直接改 head；尾插需先找到尾节点（或维护 tail 指针） |
| 埃氏筛 vs 线性筛 | 埃氏筛一个合数可能被多个素数重复标记；线性筛每个合数只被最小质因子筛一次 |
术语释义以本书正文为准；不同教材译法可能略有差异。