时间空间复杂度入门 - 实用分析方法
来源：labuladong 算法网站 侧重：复杂度分析的实用方法（简化估算技巧）
核心要点：实用估算方法
1. 大O表示法简化原则
关键规则：忽略常数项和低增长项，只保留最高增长项
| 原始表达式 | 简化后 |
|---|---|
| $O(2n^2 + 3n + 1)$ | $O(n^2)$ |
| $O(1000n + 1000)$ | $O(n)$ |
| $O(5\log n + 10)$ | $O(\log n)$ |
2. 时间复杂度快速估算
实用技巧：大部分情况下，看 for 循环的最大嵌套层数
| 嵌套层数 | 时间复杂度 |
|---|---|
| 0 层（无循环） | $O(1)$ |
| 1 层 for | $O(n)$ |
| 2 层嵌套 for | $O(n^2)$ |
| 3 层嵌套 for | $O(n^3)$ |
注意：这是简化方法，不完全准确，但对于入门和快速估算足够。
3. 空间复杂度快速估算
实用技巧：看算法申请了多少额外空间来存储数据
| 空间使用 | 空间复杂度 |
|---|---|
| 只用临时变量 | $O(1)$ |
| 创建大小为 n 的数组 | $O(n)$ |
| 创建 n×n 的二维数组 | $O(n^2)$ |
注意：输入参数不算在算法的空间复杂度内。
4. 分析原则
- 最坏情况：通常分析最坏情况下的复杂度
- n 的含义：要说明 n 代表什么（如数组长度、输入规模等）
- 越小越好：复杂度越低，算法效率越高或内存消耗越少
五个实用案例
案例 1：数组求和
- 时间：$O(n)$ — 1 层 for 循环
- 空间：$O(1)$ — 只用 sum 变量
案例 2：条件累加
- 时间：$O(n)$ — 最坏情况（n 是 10 的倍数时）
- 空间：$O(1)$
案例 3：两数之和检测
- 时间：$O(n^2)$ — 2 层嵌套 for 循环
- 空间：$O(1)$ — 只用 i, j 变量
案例 4：创建数组
- 时间：$O(n)$ — 初始化数组（隐藏的循环）
- 空间：$O(n)$ — 创建了大小为 n 的数组
案例 5：数组平方
- 时间：$O(n)$ — 1 层 for + 数组初始化
- 空间：$O(n)$ — 创建结果数组
注意事项
- 隐藏的复杂度：时间复杂度不仅体现在可见的 for 循环，每行代码都可能有隐藏开销（如数组初始化）
- 数据结构重要性：了解编程语言常用数据结构的实现原理，是准确分析复杂度的基础
- 简化 vs 严谨：本文方法是简化版，适合快速估算和入门学习
相关概念
相关实体
- labuladong：算法学习平台作者
延伸阅读
- 算法时空复杂度分析实用指南 - 更严谨完整的分析方法