Algorithm · Complexity Analysis
大 O 与 Θ · 常见量级 · 主定理 · 均摊分析 —— 面试里每道算法题的第二问
O / Ω / Θ 的精确定义，别再把"上界"当"精确量级"
主定理三 case 与递归树，以及它什么时候失灵
动态数组翻倍为什么是 O(1)，哈希表为什么"敢说" O(1)
Why It Matters
先给一个能算出结果的对照：10 万条数据去重，用 map 是 10⁵ 次操作（约 1 毫秒），用切片逐个比对是 10¹⁰ 次（约 100 秒）——同一台机器、同一个任务，差 10 万倍。
换 CPU、换语言改的是常数因子；量级 O(n) → O(n log n) → O(n²) 由算法结构决定。所以面试官不关心你机器多快，只关心规模翻 10 倍时代价怎么涨。
n 从 10⁵ 到 10⁶，O(n) 算法慢 10 倍，O(n²) 算法慢 100 倍。数据规模一给，能用的复杂度档位就锁死了（见第 11 题"规模估算"）。
排序对比、堆的建堆代价、哈希扩容、并查集近似 O(1)——每个结论都是复杂度语言写的。本篇先把这些语言规则钉死。
"这个算法是 O(1)"——哈希查找光说 O(1)，被追问最坏 O(n) 就露馅。
"平均 O(1)、最坏 O(n)，Go map 用渐进扩容把搬迁摊薄"——一句话展示三层理解。
Prerequisites & Glossary
| 术语 | 一句话理解（先记住这个，细节后面展开） |
|---|---|
| 输入规模 n | 我们讨论"代价随什么变大而变大"的那个变量。说复杂度前必须先说清 n 是谁（元素个数？位数？边数？） |
| 时间复杂度 / 空间复杂度 | 代价随 n 增长的量级，不是具体的毫秒或字节 |
| O / Ω / Θ | 渐进上界 / 下界 / 紧确界。日常说"是 O(n)"其实多半想说"是 Θ(n)" |
| 基本操作 | 我们决定去数的那个动作（一次比较、一次加法、一次哈希）。数它而不数别的，是因为它们只差常数倍 |
| 最坏 / 平均 / 均摊 | 三种取数口径：最坏=最倒霉那次；平均=对输入分布取期望；均摊=一整串操作算总账再除 |
| 递归式 recurrence | 用"规模更小的自己"来描述代价的等式，如 T(n)=2T(n/2)+O(n) |
| 主定理 | 解 T(n)=aT(n/b)+f(n) 这类分治递归式的现成公式，对照三个 case 直接出答案 |
| 递归树 / 递归深度 | 把递归一层层展开成的树；树高就是递归深度，它决定空间复杂度 |
| 均摊分析 | 对一整串操作算总代价再除以次数。它对任意操作序列都成立，不靠运气 |
| 原地 in-place | 额外空间 O(1)——不管输入多大，辅助空间是个常数 |
只要你能读懂循环、递归和数组下标就够了。想看复杂度被怎么用在真实算法上，可以对照这几篇：
排序算法 → 同一问题五种复杂度解法
二分查找 → O(log n) 从哪来的
Go slice 底层 → 均摊扩容的真实代码
把复杂度分析记成一个固定三步动作：① 选定随什么变大（n 是谁）；② 数"基本操作执行了多少次"，看它随 n 怎么长；③ 只保留增长最快的那一项，系数全部丢掉。后面所有工具——主定理、递归树、均摊分析——都只是帮你在不同结构里把第 ② 步的"数次数"做出来。
同一个算法换个 n 定义，复杂度就变了：判断质数按数值大小是 O(√N)，按二进制位数就是 O(2^(k/2))（指数级）。面试里没说清 n 就报复杂度，是最容易被追问到露馅的地方。
Asymptotic Notation · CLRS ch3
| 记号 | 定义（n → ∞） | 直觉 | 例：f(n) = 3n² + 5n + 2 |
|---|---|---|---|
| O(g) | ∃c,n₀：f(n) ≤ c·g(n) | 渐进上界：不超过 | f = O(n²) ✓，但 f = O(n³) 也"对"（只是没信息量） |
| Ω(g) | ∃c,n₀：f(n) ≥ c·g(n) | 渐进下界：不低于 | f = Ω(n²) ✓，Ω(n) 也对 |
| Θ(g) | c₁·g(n) ≤ f(n) ≤ c₂·g(n) | 紧确界：恰好这个量级 | f = Θ(n²)，且只有 Θ(n²) |
| o(g) / ω(g) | 上/下界取不到（严格） | 严格慢于 / 严格快于 | f = o(n³)，f = ω(n) |
历史习惯 + 保守承诺：O 给的是"承诺不超过"，最坏情形导向的思维对工程更安全。但面试口头表达里，说 "平均 Θ(n log n)、最坏 O(n²)" 这种混合句式最专业——哪里精确、哪里保守，清清楚楚。
Growth Ladder
| 复杂度 | 名称 | 典型算法 / 操作 | n = 10⁶ 时的量级（基准 10⁸ 简单运算/秒） |
|---|---|---|---|
| O(1) | 常数 | 数组下标访问、哈希查找（平均）、栈顶弹出 | ≈ 10ns，与 n 无关 |
| O(log n) | 对数 | 二分查找、平衡树查找、堆上浮/下沉 | ≈ 20 次运算 → 亚微秒 |
| O(n) | 线性 | 遍历、快排单轮划分、桶计数 | 10⁶ 次 → 10ms |
| O(n log n) | 线性对数 | 归并/堆排序、快排平均，比较排序的下界 | 2×10⁷ 次 → 0.2s |
| O(n²) | 平方 | 冒泡/选择/插入（平均）、朴素双指针枚举 | 10¹² 次 → ≈ 2.8 小时 |
| O(2ⁿ) | 指数 | 枚举全部子集、暴力搜索解空间 | n=40 已需数小时，n=10⁶ 不可行 |
| O(n!) | 阶乘 | 枚举全排列（TSP 暴力解） | n=15 已超 10¹²，彻底不可行 |
Growth Curves · log₂ 纵轴
How To Analyze
先 O(n) 预处理再 O(n²) 主循环 → O(n²)。低阶项与常数在大 n 下全部忽略。
内层固定 n 次就相乘；内层 j < i 则是 Σi = n(n+1)/2，仍是 O(n²)。依赖关系决定是"乘"还是"求和"。
每轮把规模除以 2（或乘以 2）→ 循环轮数是 O(log n)。二分、快速幂、i *= 2 循环都是这个形状。
把"子问题个数 × 子问题规模 + 本层代价"写成 T(n) = a·T(n/b) + f(n)，用主定理或递归树解——下两页展开。
// ② 嵌套：内层依赖外层 → 求和 for i := 1; i < n; i++ { for j := 0; j < i; j++ { // Σi = n²/2 } } // O(n²) // ③ 倍增：轮数取对数 for i := 1; i < n; i *= 2 { for j := 0; j < n; j++ { } } // O(n·log n)
i *= 2、内层 j < i，答案不是 O(n log n) 而是 O(n)：总工作量 = 1+2+4+…+n = 2n−1。求和看总账，别把两层复杂度硬乘（QA 第 10 题原题）。
Master Theorem · CLRS ch4
When Master Theorem Fails · Recursion Tree
// 自底向上建堆：从最后一个非叶节点逐个下沉 func buildHeap(a []int) { for i := len(a)/2 - 1; i >= 0; i-- { siftDown(a, i, len(a)) // 代价 = O(h(i)) } }
高度为 h 的节点至多 ⌈n/2^(h+1)⌉ 个，每个下沉 O(h)：
Σh=0⌊log₂n⌋ (n/2^(h+1)) · O(h)
= O(n) · Σ h/2^h = O(n) · 2 = O(n)
（用到 Σh≥0 h/2^h = 2，几何级数逐项求导）
把树倒过来看：一半节点是叶子（代价 0），1/4 最多沉 1 层，1/8 最多沉 2 层……代价集中在稀疏的顶层，总账被底层"稀释"到 O(n)。
堆排序先花 O(n) 建堆、再 n 次 O(log n) 下沉 → 总 O(n log n)；TopK 用建堆 O(n) + k 次弹出 O(k log n)。详见 排序 deck 与 堆 deck。
Amortized Analysis · CLRS ch17
满员时翻倍扩容、整体搬迁一次 O(n)。单看那一次是 O(n)，但任何 n 次 append 的总代价 ≤ 2n——按"序列总账"算，每次操作背负的均摊代价就是 O(1)。
n 次 push：写 n 次 + 搬 1+2+4+…+2^k < 2n 次 → 总代价 < 3n → 均摊 O(1)。最直观，面试首选。
每次 append 收 3 元：1 元付本次写入，2 元存着付未来它被搬迁的两次（2 倍扩容下每个元素最多被搬 log n 次，但按"当前存的钱"总够付）。证明了均摊 3 = O(1)。
定义势 Φ = 2·size − capacity ≥ 0；每次插入的实际代价 + ΔΦ ≤ 3。最强大也最抽象，处理"代价与状态相关"的场合（如二项堆）才必须上。
Go slice append（slice deck）、map 渐进扩容（哈希 deck）、vector push_back、splay tree、二项堆。
并查集"近似 O(1)"（α(n)，并查集 deck）、动态数组按 1.5 倍扩容仍是均摊 O(1)（几何级数通吃）。
Doubling · Aggregate Account
Amortized ≠ Average
对任意长度为 n 的操作序列，总代价 ≤ c·n。不管来的是什么序列（哪怕全是恶意构造），平均到每次都是 O(1)。动态数组 append、并查集（α(n)）属于这类——无随机性、无分布假设，铁证。
在"输入随机/散列均匀"的假设下，单次操作的期望代价是 O(1)。快排期望 O(n log n)（随机枢轴）、哈希表查找 O(1)（简单均匀散列假设）属于这类——假设一旦被打破，保证失效。
| 说法 | 成立前提 | 被恶意打爆？ | 典型例子 |
|---|---|---|---|
| 均摊 O(1) | 无（对任意序列成立） | 不能 | 动态数组 append、并查集 union |
| 平均/期望 O(1) | 散列均匀 / 输入随机 | 能——构造全碰撞键 → 单桶链 → O(n) | 哈希表查找、快排随机枢轴 |
| 最坏 O(n) | — | — | 哈希表全碰撞时的真实下界 |
Space Complexity
原地（in-place）算法 O(1) 额外空间；开辅助数组 O(n)。输入本身占多少与本算法无关。
递归深度 d 层、每帧 O(1) 局部变量 → 空间 O(d)。树递归遍历是 O(h)（h 为树高），不是 O(n)——同一时刻只有一条根到叶的路径存活在栈上。
尾递归在 Go 里不省栈（规范不保证 TCO，编译器不做）；深递归（如百万级链表）要手写迭代或分批处理，否则栈溢出。
哈希换时间（O(n) 空间换 O(n) 时间）、记忆化（空间换重复计算）、滚动数组（DP 里 O(nd) → O(d)）。面试常追问："空间能压到 O(1) 吗？代价是什么？"
| 算法 | 时间 | 额外空间 |
|---|---|---|
| 快排 | 平均 O(n log n) | O(log n) 递归栈（最坏 O(n)） |
| 归并排序 | O(n log n) | O(n) 辅助数组 |
| 堆排序 | O(n log n) | O(1)（真·原地） |
| 计数/桶排序 | O(n+k) | O(k) 桶数组（k 为值域） |
| 链表反转 | O(n) | O(1) 三指针 |
| 二叉树遍历（递归） | O(n) | O(h) 栈深（平衡 O(log n)，最坏链状 O(n)） |
Cheat Sheet · 本系列总纲
| 结构 | 访问 | 查找 | 插入 | 删除 | 关键词 & 详见 |
|---|---|---|---|---|---|
| 数组 | O(1) 下标 | O(n) | O(n) | O(n) | 尾部插入均摊 O(1)；数组与链表 |
| 链表 | O(n) | O(n) | O(1)¹ | O(1)¹ | ¹ 已定位节点的前提下；数组与链表 |
| 哈希表 | — | O(1)² | O(1)² | O(1)² | ² 平均；最坏 O(n) 全碰撞；哈希表 |
| 平衡 BST | O(log n) | O(log n) | O(log n) | O(log n) | 红黑/AVL；有序性是哈希给不了的；平衡树 |
| 跳表 | O(log n)³ | O(log n)³ | O(log n)³ | O(log n)³ | ³ 期望；Redis zset 的实现；跳表 |
| 堆 | 堆顶 O(1) | O(n) | O(log n) | 弹顶 O(log n) | TopK / 优先队列主力；堆 |
| Trie | — | O(L) | O(L) | O(L) | L 为串长，与元素总数无关；Trie |
| 并查集 | — | — | O(α(n))⁴ | 不支持 | ⁴ 近似常数，合并+查询；并查集 |
| 布隆过滤器 | — | O(k)⁵ | O(k) | 不支持 | ⁵ k 为哈希个数；可误判不漏判；布隆过滤器 |
均摊/期望/平均已分别标注；"访问"指按位置随机访问。有序场景（范围查询、TopK、前驱后继）哈希表无能为力，需要树/跳表——这是"哈希 vs 树"面试题的题眼。
Cheat Sheet
| Case | 条件（比 n^(log_b a) 和 f(n)） | 结论 |
|---|---|---|
| Case 1 | f(n) 多项式级更慢地增长 | Θ(f(n)) —— 分治外的活儿主导 |
| Case 2 | 两者同阶（差一个 log^k n） | Θ(n^(log_b a) · log^(k+1) n) |
| Case 3 | f(n) 多项式级更快地增长 + 正则条件 | Θ(f(n)) —— 递归不再是瓶颈 |
| 失灵时 | 子问题规模不等、f 不满足多项式差距 | 退回递归树 / 求和（如建堆 O(n)） |
| ① 定 n | 先说清"随什么变大"——元素个数、位数、边数？ |
| ② 数次数 | 循环看嵌套层数与上界是否跟随外层（跟随要求和，不是相乘） |
| ③ 只留最大项 | 3n²+5n+2 → Θ(n²)；系数、低阶项、log 底数全部丢掉 |
| ④ 分开口径 | 平均与最坏分开说；有扩容/缩容的补一句均摊 |
| 口径 | 成立前提 | 典型例子 |
|---|---|---|
| 最坏 | 无（对任意输入都成立） | 快排 O(n²)、哈希 O(n) |
| 平均 / 期望 | 依赖输入分布或随机性假设 | 快排期望 O(n log n)、哈希平均 O(1) |
| 均摊 | 无——对任意操作序列成立 | 动态数组 append O(1)、并查集 O(α(n)) |
| n ≤ 10³ | O(n²) 随便写；O(2ⁿ) 也可一试 |
| n ≤ 10⁵ | O(n log n) 稳过；O(n²) 基本挂 |
| n ≤ 10⁶ | 只剩 O(n) 与 O(n log n) |
| n ≤ 20 / 12 | 条件反射想到 O(2ⁿ) 状压回溯 / O(n!) 全排列 |
Interview QA · Part 1
先自答，再对照：每题先说出你的答案（哪怕只说关键词），再展开下面那行——卡住的那 30 秒才是真正长记性的部分。
O 只是上界（冒泡排序也是 O(n!)），Θ 才是精确量级。严谨说法：快排期望 Θ(n log n)、最坏 Θ(n²)。能补一句"随机枢轴时期望成立"更佳。
插入排序：已有序输入 O(n)，逆序 O(n²)。只说一个数字 = 丢弃了算法对输入的敏感度；面试官要的是你知道它在什么输入下退化。
前者 n^(log₂4)=n² 主导 → Θ(n²)；后者 f=n log n 与 n 同阶但多一个 log（Case 2 的 k=1 变体）→ Θ(n log²n)。第二问专考你有没有背"主定理扩展形式"。
建堆不是"划分-递归-合并"结构，是按高度求和 Σ (n/2^(h+1))·O(h) = O(n)。硬套"每层 O(n)×log n 层"会把底层海量低代价节点错算成 O(n log n)。
均摊：任意序列总代价/次数，无假设、有硬保证（动态数组）；平均：依赖输入分布/散列均匀假设的期望值（哈希表），假设被打破就退化。
平均 O(1) 建立在散列均匀 + 负载因子受控上；最坏全碰撞 O(n)。工程上用好的散列函数 + 扩容/树化兜底（Java 8 链表超 8 转红黑树，最坏降到 O(log n)）。
输入不计（那是问题规模），递归栈必须算：递归深度 d、每帧 O(1) → O(d)。树递归遍历是 O(h)——同一时刻只有一条路径在栈上。
快排：递归栈平均 O(log n)、最坏 O(n)（划分极不均匀）；归并：O(log n) 栈 + O(n) 辅助数组，相加取最大 → O(n)。堆排 O(1) 是三者中唯一真原地。
Interview QA · Part 2
先自答，再对照。这一组的重点是"能推"——先把答案自己算出来，再看下面那行验证你的步骤对不对。
k 轮后剩余 n/2^k，停机条件 n/2^k ≤ 1 → k ≥ log₂n。反过来写循环不变量：区间长度 L 每轮至少减半，L 从 n 到 1 的减半次数就是 log₂n。
总工作量 = 1+2+4+…+<n = 2n−1 → O(n)，不是 O(n log n)。内层上界跟外层走时必须求和；只有内层独立满 n 次才是乘出 O(n log n)。
1 秒 ≈ 10⁸ 简单运算：n=10⁵ → O(n log n)（≈1.7×10⁶）稳、O(n²)（10¹⁰）悬；n=10⁶ → O(n log n) 尚可、O(n²) 必挂。从数据规模反推可行档位，是选题第一步。
n 次 push 总搬迁 = 1+2+4+…+2^k < 2n（几何级数被末项主导），加 n 次写入总代价 < 3n → 均摊 O(1)。关键在倍增：改成固定 +10 增量就是均摊 O(n)。
记账：动态数组每次 push 收 3 元（1 写 + 2 搬），任意时刻累计余额 ≥ 0 → 均摊 3。势能：Φ=2·size−capacity ≥ 0，摊还代价 = 实际代价 + ΔΦ ≤ 3。势能法适合状态相关的场合（二项堆、splay）。
时间 = 递归树节点数 × 每节点代价（解递归式）；空间 = 同时存活的最大栈深 × 每帧空间。二叉树 DFS：时间 O(n)，空间 O(h)——两者根本不是一回事。
换底公式 log₁₀n = log₂n / log₂10，只差常数因子，Θ 意义下等价。但 O(2^log n) = O(n) 这种"对数在指数上"不能乱约——底数在指数里就不再是常数因子了。
Related & References
排序算法 →（各排序复杂度全景，比较排序下界）
二分查找 →（O(log n) 的代表选手）
动态规划 →（记忆化 = 时空交换的典型）
回溯 →（O(2ⁿ)/O(n!) 解空间的代表）
数组与链表 →（动态数组均摊扩容的实体）
哈希表 →（平均 O(1) 的成立前提）
堆与优先队列 →（建堆 O(n) 的主场）
Go slice 底层 →（growslice 扩容工程实现）
参考来源（本 deck 结论可溯源至下列一手材料）
| CLRS《Introduction to Algorithms》ch3/ch4/ch17 | 渐进记号定义 · 主定理与递归树 · 均摊分析三方法 |
| oi-wiki.org/basic/complexity | 复杂度入门：量级、主定理、均摊（中文对照） |
| bigocheatsheet.com | 数据结构/排序操作复杂度速查表（本 deck 第 13 页同源） |
| Cornell CS3110 · Lecture 20: Amortized Analysis | 聚合/记账/势能三方法的独立讲义佐证 |
| GeeksforGeeks · Introduction to Amortized Analysis | 动态数组三方法算例（与 CLRS ch17 互勘） |