复杂度分析

1. 一句话总结

复杂度描述算法随输入规模增长时的资源消耗趋势，重点不是精确计时，而是判断增长速度。

2. 通俗解释

O(n) 像逐个检查，O(n²) 像两两比较，O(log n) 像每次砍掉一半。面试分析复杂度，是看数据变大后谁增长更快。

3. 核心概念

• 时间复杂度：执行步骤随 n 的增长趋势。
• 空间复杂度：额外内存随 n 的增长趋势。
• 大 O：保留最高阶，忽略常数和低阶项。
• 递归复杂度：看递归次数、每层代价和栈深度。
• 摊还复杂度：把少数昂贵操作分摊到多次操作中。

4. 底层原理

• 单层循环通常 O(n)，完整双层循环通常 O(n²)。
• 二分、堆、平衡树常见 O(log n)，因为规模按比例缩小。
• 哈希表平均 O(1)，但冲突严重可能退化。
• 递归空间要算调用栈，链状递归最坏 O(n)。
• 动态数组扩容单次 O(n)，连续插入摊还 O(1)。

5. 面试标准回答

复杂度分析关注输入规模扩大时资源消耗的增长趋势。时间复杂度描述执行步骤数量，空间复杂度描述额外内存占用。分析时通常忽略常数和低阶项，只保留最高阶。单层循环是 O(n)，完整双层循环是 O(n²)，二分查找每次缩小一半所以是 O(log n)。递归要看调用次数、每层代价和递归栈空间。扩容类操作单次可能很贵，但连续操作可用摊还复杂度解释。

6. 高频追问

追问 1：复杂度分析面试第一句话怎么答？

先给结论：时间复杂度：执行步骤随 n 的增长趋势。 再补充它解决的问题和使用场景，避免一上来背长定义。

追问 2：它为什么需要底层机制支撑？

单层循环通常 O(n)，完整双层循环通常 O(n²)。 面试官追问时要把“现象”落到“机制”和“代价”。

追问 3：常见误区是什么？

不要把平均情况说成绝对结论，也不要忽略边界条件、退化情况和工程成本。

追问 4：如果继续追问怎么展开？

可以沿着“定义 → 原理 → 对比 → 场景 → 缺点 → 优化”展开，重点说清：二分、堆、平衡树常见 O(log n)，因为规模按比例缩小。

追问 5：实际开发中怎么体现？

接口处理大批量数据时，O(n²) 可能导致超时。 这类联系能把基础知识从“背概念”变成“解释工程选择”。

追问 6：回答时怎么收尾？

最后用一句话总结适用条件和代价，说明什么时候该用、什么时候不该用。

7. 易混淆点

8. 实际开发联系

• 接口处理大批量数据时，O(n²) 可能导致超时。
• 数据库从全表扫描到索引查询，本质是复杂度和 IO 次数下降。
• 缓存查询希望接近 O(1)，但也要考虑冲突和内存。

9. 背诵速记

复杂度看增长趋势。单循环 O(n)，双循环 O(n²)，二分 O(log n)，排序常见 O(nlogn)，哈希表平均 O(1)。递归要看调用次数、每层代价和栈深度，扩容常用摊还分析。