【数据结构与算法】第4篇：算法效率衡量：时间复杂度和空间复杂度
一、写在前面
上一篇我们学会了动态内存管理，从这篇开始，要真正进入算法的世界了。
在写具体的算法之前，先要解决一个问题：怎么衡量一个算法的好坏？
两个程序员写了两个排序程序，一个跑得快，一个跑得慢，怎么定量地比较？这就引出了我们今天的主角——时间复杂度和空间复杂度。
二、什么是时间复杂度
时间复杂度不是指程序跑了多少秒。因为运行时间跟硬件、编译器、当前系统负载都有关系，同一段代码在不同机器上跑出来的时间可能差很多。
我们关心的是：当数据规模变大时，算法执行时间的增长趋势。
2.1 大O渐进表示法
大O表示法用来描述算法的时间复杂度，它忽略常数项和低阶项，只保留最高阶。
常见的大O复杂度从低到高：
| 复杂度 | 名称 | 例子 |
|---|---|---|
| O(1) | 常数阶 | 数组按索引取值 |
| O(log n) | 对数阶 | 二分查找 |
| O(n) | 线性阶 | 遍历数组 |
| O(n log n) | 线性对数阶 | 快速排序、归并排序 |
| O(n²) | 平方阶 | 冒泡排序、选择排序 |
| O(2ⁿ) | 指数阶 | 斐波那契递归 |
画个图理解增长趋势（n=10时）：
text
n = 10: O(1) → 1 O(log n) → 约3 O(n) → 10 O(n log n) → 约33 O(n²) → 100 O(2ⁿ) → 1024 n = 100: O(1) → 1 O(log n) → 约7 O(n) → 100 O(n log n) → 约664 O(n²) → 10000 O(2ⁿ) → 天文数字
n越大，差距越明显。这就是为什么算法设计这么重要。
2.2 大O的计算规则
规则1：只保留最高阶项
c
// 3次操作 + 1次循环（n次）+ 1次操作 // 总操作次数：n + 4 // O(n) for (int i = 0; i < n; i++) { printf("%d\n", i); // 执行n次 } printf("done\n"); // 1次规则2：常数系数忽略
c
// 2n次操作，还是O(n) for (int i = 0; i < n; i++) { printf("%d\n", i); // n次 printf("%d\n", i); // 又是n次 }规则3：加法法则，取最高阶
c
// 第一部分：O(n) for (int i = 0; i < n; i++) { ... } // 第二部分：O(n²) for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { ... } } // 整体：O(n + n²) = O(n²)规则4：乘法法则，嵌套相乘
c
// 外层n次，内层m次 for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { ... } } // 复杂度：O(n * m)三、最好、最坏、平均情况
同一个算法，输入不同，执行时间可能不一样。
以顺序查找为例：
c
int search(int arr[], int n, int target) { for (int i = 0; i < n; i++) { if (arr[i] == target) return i; } return -1; }最好情况：第一个元素就是要找的，O(1)
最坏情况：最后一个元素才是，或者没找到，O(n)
平均情况：假设目标在每个位置概率相等，平均比较次数 n/2，还是O(n)
写算法时，我们通常关心最坏情况，因为它给出了一个上界保证。
四、空间复杂度
空间复杂度衡量算法运行时额外占用的内存（输入本身占的空间不算）。
c
// O(1) 空间复杂度，只用了几个变量 int sum(int arr[], int n) { int total = 0; // 1个变量 for (int i = 0; i < n; i++) { // i又是一个 total += arr[i]; } return total; }c
// O(n) 空间复杂度，申请了n个int的空间 int* copyArray(int arr[], int n) { int *newArr = (int*)malloc(n * sizeof(int)); for (int i = 0; i < n; i++) { newArr[i] = arr[i]; } return newArr; }递归的空间复杂度：每次递归调用都会在栈上分配空间，递归深度是多少，空间复杂度就是多少。
五、经典例子实战
5.1 二分查找
c
int binarySearch(int arr[], int n, int target) { int left = 0, right = n - 1; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == target) return mid; else if (arr[mid] < target) left = mid + 1; else right = mid - 1; } return -1; }分析：
每次循环，搜索范围缩小一半
n, n/2, n/4, ... 直到1
需要循环 log₂n 次
时间复杂度：O(log n)
为什么log n这么快？n=100万时，log₂n ≈ 20，只需要20次比较。
5.2 斐波那契数列（递归版）
c
int fib(int n) { if (n <= 1) return n; return fib(n - 1) + fib(n - 2); }画出递归树（n=5为例）：
text
fib(5) / \ fib(4) fib(3) / \ / \ fib(3) fib(2) fib(2) fib(1) / \ / \ / \ fib(2) fib(1) ... ... ...
分析：
每个节点分出两个子节点
节点总数 ≈ 2ⁿ
很多重复计算，fib(2)被算了多次
时间复杂度：O(2ⁿ)
n=50时，2⁵⁰ ≈ 1亿亿，根本跑不完。这就是指数级复杂度的可怕之处。
5.3 斐波那契数列（迭代版）
c
int fib(int n) { if (n <= 1) return n; int a = 0, b = 1, c; for (int i = 2; i <= n; i++) { c = a + b; a = b; b = c; } return b; }分析：
循环执行 n-1 次
每次只做常数次操作
时间复杂度：O(n)
空间复杂度：O(1)
同样的功能，从O(2ⁿ)优化到O(n)，这就是好算法和烂算法的差距。
六、复杂度对比表
| 算法 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 数组按索引访问 | O(1) | O(1) |
| 顺序查找 | O(n) | O(1) |
| 二分查找 | O(log n) | O(1) |
| 冒泡排序 | O(n²) | O(1) |
| 快速排序 | O(n log n) 平均 | O(log n) |
| 归并排序 | O(n log n) | O(n) |
| 斐波那契（递归） | O(2ⁿ) | O(n)（递归栈） |
| 斐波那契（迭代） | O(n) | O(1) |
七、实际开发中的取舍
复杂度分析不是纸上谈兵，实际开发中经常需要权衡：
时间换空间：比如缓存一些计算结果，用内存换时间。
c
// 不缓存：每次都重新计算 int getValue(int index) { return heavyCalculation(index); // 耗时 } // 缓存：算过的存起来 int cache[1000]; int getValue(int index) { if (cache[index] == 0) { cache[index] = heavyCalculation(index); } return cache[index]; }空间换时间：比如哈希表，用额外内存换来O(1)的查找速度。
选择哪种，要看具体场景：
内存紧张（嵌入式）→ 优先省空间
响应速度要求高（Web服务）→ 优先省时间
八、小结
这一篇我们讲了：
| 概念 | 要点 |
|---|---|
| 时间复杂度 | 算法执行时间随数据规模的增长趋势 |
| 空间复杂度 | 算法额外占用的内存随数据规模的增长趋势 |
| 大O表示法 | 忽略常数和低阶项，只保留最高阶 |
| 最好/最坏/平均 | 不同输入下的表现，通常关注最坏情况 |
| 常见复杂度 | O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) |
重点记住：
二分查找 O(log n)，比 O(n) 快得多
递归不总是好选择，斐波那契用递归是 O(2ⁿ)，用迭代是 O(n)
实际开发中，时间和空间经常需要取舍
九、思考题
下面代码的时间复杂度是多少？
c
for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { printf("%d %d\n", i, j); } }下面代码的时间复杂度是多少？
c
int i = 1; while (i < n) { i = i * 2; }判断对错：O(n²) 一定比 O(n) 慢。
如果要在一个有序数组中查找一个数，你会选择顺序查找还是二分查找？为什么？
欢迎在评论区讨论你的答案。