外观
时间复杂度和空间复杂度怎么算？
时间复杂度描述操作次数怎么随数据规模增长，空间复杂度描述额外内存怎么增长。看的是增长趋势，不是某台机器上的毫秒数。
原理
大 O 取增长最快的那一项，常数和低阶项丢掉。一层从 0 到 n 的循环是 O(n)。循环里再对剩余区间扫描，常常是 O(n²)。每次把问题砍半，是 O(log n)。二叉树每个节点访问一次是 O(n)。
排序的比较次数：冒泡、选择、插入最坏 O(n²)。归并稳定在 O(n log n)，需要额外 O(n) 空间。快速排序平均 O(n log n)，最坏 O(n²)，额外栈空间平均 O(log n)。
空间看额外开辟的结构。递归深度也算空间，因为它占执行栈。原地算法的额外空间是 O(1)，输入本身不计入。
前端里，DOM 节点数量、一次渲染创建的对象，同样用这个语言描述。一千行的列表如果每个格子都绑重组件，成本按可见节点而不是「算法题的 n」来估，见 无限列表。
追问
最好、最坏、平均？
快速排序的最坏出现在划分极不均匀时。面试要说清是哪一种。平均如果依赖数据分布，要说明假设。
O(n) 一定比 O(n log n) 快吗？
n 很小或常数差很大时，不一定。复杂度用来比较规模变大之后的趋势。真正的卡顿用测量确认。
易错点
- 把两层固定次数的循环说成 O(n²)。内层如果和 n 无关，仍是 O(n)。
- 递归只分析时间，不分析栈深度。
- 用复杂度代替性能面板。一次 O(n) 的布局可能比一次 O(n log n) 的排序更贵。