📏 复杂度分析
大 O 记号 · 常见复杂度 · 递归与 Master 定理 · 空间复杂度
1. 什么是大 O 复杂度？如何推导？
大 O：描述算法运行时间随输入规模 n 增长的量级趋势（渐进上界）。忽略常数和低阶项。
推导三步：
- 只关注最高阶项：3n² + 5n + 8 → O(n²)
- 忽略系数：2n → O(n)
- 循环嵌套相乘、顺序相加：两层循环 O(n²)，先 O(n) 后 O(n) 还是 O(n)
常见复杂度排序（快→慢）：
O(1) < O(log n) < O(√n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)
- O(log n)：二分查找、平衡树操作
- O(n log n)：快排/归并/堆排、多数排序
- O(2ⁿ)：子集枚举、部分回溯
- O(n!)：全排列
🎯 面试要点
- 判断循环：
for (i=1; i<n; i*=2)→ O(log n)；两层独立循环 → O(n·m) 或 O(n²) - 面试讲复杂度要讲最坏情况（除非题目要求均摊/平均）
- Hash 操作均摊 O(1)，最坏 O(n)（大量冲突）——答"均摊 O(1)"更严谨
2. 递归算法的复杂度怎么算？
方法：递归树或 Master 定理。关键看每层调用数 × 每层工作量：
- 二叉递归（每层 2 个调用）：斐波那契朴素递归 O(2ⁿ)，记忆化后 O(n)
- 单分支递归：O(深度 × 每层工作量)
- Master 定理（分治 T(n) = a·T(n/b) + f(n)）：
- f(n) < n^log_b(a) → T(n) = Θ(n^log_b(a))
- f(n) = n^log_b(a) → Θ(n^log_b(a) · log n)
- f(n) > n^log_b(a) → Θ(f(n))
🎯 面试要点
- 记忆化搜索 = 递归 + 缓存：时间 = 状态数 × 每状态耗时（DP 复杂度分析的口径）
- 回溯的复杂度：解空间大小 × 每解构造成本——答"最坏 O(2ⁿ·n)"这类才严谨
3. 空间复杂度分析要点？
- 额外开辟的存储（数组、哈希、递归栈深度）计入；输入数组本身不算"额外"
- 递归深度 = 空间（如快排最坏 O(n) 栈深、平衡时 O(log n)）
- 原地算法（in-place）：空间 O(1)，如原地快排/堆排
- 滚动数组优化：DP 二维 → 一维，空间 O(n²) → O(n)
🎯 面试要点
- "额外空间 O(1)"与"总空间"要分清楚，面试官常抠这个
- 能原地就原地（如双指针原地去重），空间优化是加分动作