算法复杂度分析
一句话总结
本文提供一套通用的算法时空复杂度分析方法，重点讲解如何利用数据规模反推解题思路、避免编码失误，以及 大O表示法的实用特性。
核心要点
1. 借助复杂度反推解题思路
留意数据规模：在开始写代码前应关注题目给定的数据规模，通过复杂度反推算法方向。
- 数组长度达 10⁶ 量级 → 需要 O(N) 或 O(NlogN)，排除嵌套循环、二维 dp、回溯等
- 数组长度 N ≤ 20 → 大概率需要暴力穷举（回溯算法），最优解可能是指数/阶乘级复杂度
判题平台给小数据规模，往往是因为最优解复杂度本身很高，直接用回溯算法即可。
2. 编码失误导致复杂度异常
三个常见错误：
| 错误类型 | 说明 | 影响 |
|---|---|---|
| 使用标准输出 | print/console.log 属于 I/O 操作 | 严重拖慢运行速度 |
| 错误传值而非传引用 | C++ 中 vector 参数默认传值会复制 | 递归函数尤其容易超时/超内存 |
| 接口对象底层实现不明 | Java List 接口可能是 ArrayList 或 LinkedList | get 方法复杂度可能是 O(1) 或 O(N) |
建议：Java 中遇到 List 参数，先复制到 ArrayList 再随机访问。
3. 大O表示法的两个关键特性
特性一：只保留增长速率最快的项
O(2N + 100) = O(N)
O(2^(N+1)) = O(2^N)
O(N^3 + 999*N^2) = O(N^3)
O((N+1)*2^N) = O(N*2^N)
注意：常数因子通常可忽略，但指数中的常数不能消（O(2^(2N)) = O(4^N)）。
特性二：大O表示法表示复杂度的上界
- O(N) 算法也可以说成 O(N²)，只是上界不够"紧"
- 对于输入相关的算法（如凑零钱递归），按最坏情况近似：K 种硬币、金额 N → 满 K 叉树，节点数 O(K^N)
- 实际分析时，数量级正确（线性/指数级/对数级）即可，不必过分追求精确
基本原理
递归算法复杂度分析思路
文章以凑零钱问题为例，递归树分析：
![[raw/images/复杂度分析_递归树.jpg]]
- 假设 coins 有 K 个元素，amount = N
- 最坏情况：全为面额 1 的硬币，树高 N
- 最坏结构：满 K 叉树
- 节点总数：(K^N - 1)/(K - 1) = O(K^N)
时间复杂度
| 场景 | 时间复杂度 | 说明 |
|---|---|---|
| 简单循环 N 次 | O(N) | 线性 |
| 嵌套循环 | O(N²) | 平方级 |
| 分治/排序 | O(NlogN) | 对数线性 |
| 回溯穷举 | 指数级 | 取决于状态空间 |
| 凑零钱暴力递归 | O(K^N) | K=硬币种类数 |
相关概念
- 时间复杂度：算法运行时间与输入规模的关系
- 空间复杂度：算法占用空间与输入规模的关系
- 大O表示法：描述复杂度上界的数学记号
- 摊还分析：
总结
复杂度分析不仅是评判标准，更是解题帮手——通过数据规模反推算法方向可大幅减少试错时间。大O表示法关注增长最快项和上界特性，实际分析中数量级正确即可。注意避免编码层面的性能陷阱。
待补充
由于原文无法完整获取（在"非递归算法分析"处截断），以下内容缺失：
- 完整的非递归算法时间复杂度分析方法
- 数据结构 API 效率衡量方法（摊还分析）
- 递归算法的时间/空间复杂度详细分析（动态规划、回溯算法举例）
- 可能的其他章节内容