5分钟彻底搞懂时间复杂度与空间复杂度（C语言版）

复杂度分析就像“给算法做体检”——不用跑代码，就能提前判断程序能不能扛住大数据。
本文用最生活化的例子 + C 语言代码，帮你一口气掌握大O、时间复杂度、空间复杂度。

一、为什么需要复杂度分析？

假如你写了一个排序，100 个数据很快，但 100 万个数据直接卡死——问题就出在算法效率上。
大 O 表示法 关注的是数据规模 n 变得非常大时，执行次数或空间占用的增长趋势，而不是具体秒数。

二、时间复杂度 (Time Complexity)

1. 什么是大 O ？

大 O 只统计核心代码执行次数的数量级。
规则：忽略常数、系数和低阶项，只保留最高阶。
例如执行次数 3n² + 2n + 100，时间复杂度就是 O(n²)。

2. 快速推导方法

找出代码中执行次数最多的语句，看它随着 n 如何增长。

3. 常见时间复杂度（C 语言代码示例）

🔹 O(1) – 常数阶

int get_first(int arr[]) {
return arr[0]; // 不管数组多大，只执行一次
}
就像从书架拿第一本书，和书的总量无关。函数只接收数组指针，完全不关心数组大小。

#### 🔹 O(log n) – 对数阶（二分查找）
```c
int binary_search(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;
}

每次砍掉一半数据，数据量翻倍只会多执行一次。查字典就是二分思想。

🔹 O(n) – 线性阶

void print_all(int arr[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]); // 有 n 个元素就执行 n 次
}
}

像抄写名单，人越多花的时间越长。

🔹 O(n log n) – 线性对数阶

归并排序、快速排序的典型复杂度，可以理解为：每层处理 n 个元素，一共有 log n 层，总操作量 n × log n。

🔹 O(n²) – 平方阶（冒泡排序）

void bubble_sort(int arr[], int n) {
for (int i = 0; i < n – 1; i++) {
for (int j = 0; j < n – i – 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}

双重嵌套循环，数据量增大 10 倍，执行次数增大 100 倍。

🔹 O(2ⁿ) – 指数阶（递归斐波那契）

int fib(int n) {
if (n <= 1)
return n;
return fib(n – 1) + fib(n – 2);
}

这种递归像细胞分裂，n=40 时程序就基本跑不动了，一定要避免。

4. 计算技巧速记

• 单层循环 → O(n)
• 两层嵌套循环 → O(n²)
• 循环中每次规模减半 → O(log n)
• 递归调用两次及以上且不记忆 → 常是指数级
• 只保留最大量级，去掉常数和系数

三、空间复杂度 (Space Complexity)

空间复杂度衡量的是临时额外占用的存储空间，同样用大 O 表示。
关注：变量、数组、递归栈等，输入数据本身不算。

🔸 O(1) 空间

int sum_arr(int arr[], int n) {
int total = 0; // 只有一个临时变量
for (int i = 0; i < n; i++) {
total += arr[i];
}
return total;
}

无论数据多大，额外空间恒定。

🔸 O(n) 空间（动态开辟数组）

#include <stdlib.h>
int* copy_arr(int arr[], int n) {
int* new_arr = (int*)malloc(n * sizeof(int)); // 开辟 n 个 int 空间
for (int i = 0; i < n; i++) {
new_arr[i] = arr[i];
}
return new_arr; // 调用者记得 free
}

临时数组大小随着 n 线性增长。

🔸 递归中的空间陷阱

int fact(int n) {
if (n == 1) return 1;
return n * fact(n – 1); // 每次调用都会压栈，深度为 n
}

递归栈的深度为 n，空间复杂度就是 O(n)。
（如果递归深度过大可能造成栈溢出，这也是空间复杂度的现实意义。）

四、时间 vs 空间：如何取舍？

“鱼和熊掌”的现实：

• 追求更快 → 可能要用缓存、多存中间结果 → 空间消耗上升
• 内存紧张 → 偏向原地操作、少开辟新数组 → 时间可能变长

经典例子“两数之和”：

• 暴力双层循环 → O(n²) 时间，O(1) 空间
• 哈希表查找 → O(n) 时间，O(n) 空间

实际开发中根据数据量和硬件条件灵活平衡。

五、一张图总结

掌握这两个复杂度，刷题、面试、写项目都能游刃有余。
希望这篇 C 语言版讲解能帮你彻底打通“任督二脉”！

如果觉得有帮助，欢迎点赞收藏，让更多伙伴看到~