怎么分析时间和空间复杂度？
算法工程师第 9 / 15 题答题框架
参考思路：循环规模与输入关系→递归(主定理/递归树)→均摊(动态数组)→空间含递归栈。现场推导而非背结论。
五个经典回答示范
回答一 · 思路口述版
「复杂度是输入规模趋于无穷时算法开销的增长阶。分析要点：顺序结构取最大项、循环看乘积、递归画递归树或用主定理。空间复杂度要算上递归栈。均摊分析比如动态数组 push_back——单次可能 O(n) 但连续 n 次总 O(n)，均摊 O(1)。」
回答二 · 标准写法
现场推导示例：快排平均——每层划分 O(n)、期望 logn 层得 O(nlogn)，最坏有序输入退化 O(n²)；归并稳定 O(nlogn) 但要 O(n) 辅助空间；堆排 O(nlogn) 原地但缓存不友好。主定理记结论：T(n)=2T(n/2)+O(n) 是 O(nlogn)，二分是 T(n)=T(n/2)+O(1) 得 O(logn)。
回答三 · 进阶变体
进阶话题三块：一是复杂度符号族——大 O 上界、大 Θ 紧界、大 Ω 下界的区别，面试说清楚体现理论功底；二是常数与缓存——同为 O(nlogn) 的归并与堆排实际差数倍，体现工程判断；三是数据结构操作的复杂度表要熟——跳表查询 O(logn)、并查集近似 O(1)（路径压缩加按秩合并的均摊反阿克曼）。
回答四 · 边界与测试
分析时主动声明输入分布：快排最坏在有序输入、哈希冲突在攻击性构造下退化。被问「这段代码复杂度」时先确认 n 指什么——节点数还是边数，字符串长度还是次数。把变量含义写清楚再给结论，避免面试官挑歧义。
回答五 · 常见错误
错误一：说哈希表查询永远是 O(1)——不讲冲突与最坏 O(n)。错误二：递归算法空间说成 O(1)——忘算调用栈。错误三：双层循环必说 O(n²)——内层如果有二分是 O(nlogn)。点评：复杂度分析是算法面的通用基础功，错这里所有手撕题的评估都降档。
怎么练这道题
- 打开 模拟练习，选择「算法工程师」方向，限时 3 分钟作答本题。
- 对照上方答题框架，逐点检查：哪些要素没覆盖、哪里表达啰嗦。
- 用自己项目的真实经历替换框架中的占位内容，重讲一遍并录音回听。
这类题在真实面试中常被追问细节，
建议进入限时模式练一遍。