公告
欢迎来到我的博客！
931 字
5 分钟
⏰ 时间与空间复杂度解析
📊 算法效率的“两面性”：时间与空间复杂度全解析
1️⃣ 如何衡量算法好坏？
举个栗子🌰：斐波那契数列的递归实现
public static long Fib(int N) { if(N < 3) return 1; return Fib(N-1) + Fib(N-2);}问题：这个算法像“树懒”一样慢！为什么？
答案：因为它重复计算了大量子问题，时间复杂度高达O(2^N)！
直观感受：为什么递归这么慢？ 试算Fib(5)的执行过程：
Fib(5)├── Fib(4)│ ├── Fib(3)│ │ ├── Fib(2)│ │ └── Fib(1)│ └── Fib(2)└── Fib(3) ├── Fib(2) └── Fib(1)惊人发现：
Fib(3)被计算了2次
Fib(2)被计算了3次
当N=20时，Fib(1)会被计算6765次！2️⃣ 时间复杂度：算法的“速度表”⏱️
📌 核心思想
- 基本操作次数决定算法速度
- 大O表示法：抓主要矛盾（最高阶项）
🧮 大O三定律
- 常数变1：
F(N)=2N+10→O(N) - 只留最高阶：
O(N² + N)→O(N²) - 去除系数：
O(2N)→O(N)
🌟 经典例题分析
| 代码示例 | 执行次数 | 时间复杂度 | 类比 |
|---|---|---|---|
| 双重循环 | N² + 2N +10 | O(N²) | 全班同学两两握手🤝 |
| 单循环+固定循环 | 2N + 10 | O(N) | 点名签到📝 |
| 二分查找 | log₂N | O(logN) | 对折纸找名字📜 |
| 斐波那契递归 | 2^N | O(2^N) | 细胞分裂爆炸增长💥 |
3️⃣ 空间复杂度：算法的“储物柜”🗄️
📌 核心思想
- 临时变量数量决定内存占用
- 递归深度=空间复杂度
🧮 冒泡排序的空间复杂度分析：为什么是O(1)？
## 🔍 冒泡排序```javavoid bubbleSort(int[] array) { for (int end = array.length; end > 0; end--) { boolean sorted = true; // 变量1 for (int i = 1; i < end; i++) { if (array[i - 1] > array[i]) { Swap(array, i - 1, i); // 临时变量在Swap内 sorted = false; // 修改变量1 } } if (sorted == true) break; }}🧳 实例对比
| 变量名 | 类型 | 数量 | 生命周期 | 是否随输入规模变化 |
|---|---|---|---|---|
| end | int | 1 | 外层循环 | ❌ 固定4字节 |
| sorted | boolean | 1 | 每次外层循环 | ❌ 固定1字节 |
| i | int | 1 | 内层循环 | ❌ 固定4字节 |
| Swap | 临时变量 int | 1 | 交换瞬间 | ❌ 固定4字节 |
💡 关键结论
-
固定数量变量：无论输入数组多大（N=100或N=1,000,000），都只使用：
- 3个基本类型变量（end/sorted/i）- 1个交换用的临时变量 -
不依赖输入规模：变量数量与数组长度array.length完全无关
-
原地排序算法：直接在原数组上操作，不需要额外存储空间
🆚 对比其他排序算法
| 算法类型 | 空间复杂度 | 内存使用特点 |
|---|---|---|
| 冒泡排序 | O(1) | 只用固定几个变量🔘 |
| 斐波那契数组 | O(N) | 需要N长度的数组📊 |
| 阶乘递归 | O(N) | 递归调用N层栈帧📚 |
4️⃣复杂度权衡的艺术
- 时间换空间：比如用哈希表加速查询
- 空间换时间：比如动态规划存储中间结果
💡 现代编程箴言：
在内存充足的今天，我们更关注时间复杂度优化，
但处理海量数据时，空间复杂度依然关键！
📚 课后小测验
-
下列哪个时间复杂度最快？
A. O(N!)
B. O(N²)
C. O(log(N))
D. O(2^N) -
递归计算阶乘时，空间复杂度为什么是O(N)？
（答案：C 因为要保存N层递归调用栈）
🎯 总结
复杂度分析就像给算法做“体检”：
- 时间复杂度=心肺功能（跑得快不快）
- 空间复杂度=胃容量（吃得多不多）
