【初阶数据结构06】——时间复杂度空间复杂度详解与例题分析
文章目录
引言
在上一篇文章中，我们完成了双向链表的学习，实现了带头双向循环链表的各种操作。然而，在编程实践中，我们不仅要实现功能，还要关注程序的运行效率。同样的任务，不同的算法可能带来天壤之别的执行时间或内存消耗。那么，如何客观地衡量一个算法的好坏呢？
计算机科学引入了时间复杂度和空间复杂度这两个概念，它们像一把标尺，帮助我们定量分析算法的效率。无论是日常开发还是求职面试，理解复杂度都是程序员必备的核心素养。
1. 算法效率
1.1 什么是好的算法？
看一个简单的例子：斐波那契数列的递归实现。
long long Fib(int N) { if (N < 3) return 1; return Fib(N-1) + Fib(N-2); }代码非常简洁，但它真的高效吗？当 N 较大时，程序会变得极其缓慢，甚至可能导致栈溢出。简洁 ≠ 高效。
1.2 算法的复杂度
算法在编写成可执行程序后，运行时需要耗费时间资源和空间（内存）资源。因此，我们通常从两个维度衡量算法：
- 时间复杂度：算法运行所消耗的时间，随问题规模增长的变化趋势。
- 空间复杂度：算法运行所需的额外内存空间，随问题规模增长的变化趋势。
早期计算机内存很小，人们非常在意空间占用。如今硬件发展迅速，内存变得廉价，我们更关注时间复杂度，但空间复杂度在嵌入式等资源受限场景依然重要。
1.3 复杂度在校招中的考察
在技术面试中，复杂度分析是必考题。以下是一份真实面试经历（摘自网络）：
一面（2小时）vector扩容机制红黑树了解吗，红黑树的插入、删除（直接放弃）hash冲突是什么，如果单链长度太长怎么办快排堆排归并时间复杂度，快排最坏的情况，怎么推导的进程间通信的区别...三个编程题：strstr，堆排，实现hash的插入、查询、删除
...
可以看到，排序算法的时间复杂度、最坏情况分析等是面试高频点。掌握复杂度分析，能让你在面试中游刃有余。
2. 时间复杂度
2.1 概念
时间复杂度不是一个精确的运行时间（因为运行时间受机器、语言、编译器影响），而是一个函数，它定量描述了算法执行时间随输入规模增长的趋势。我们通常用算法中基本操作的执行次数来代表时间复杂度。通俗地讲，就是看程序的操作次数，看后面几个例子来理解一下。
例如，计算下面函数中 ++count 语句的执行次数：
void Func1(int N) { int count = 0; for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { ++count; } } for (int k = 0; k < 2 * N; ++k) { ++count; } int M = 10; while (M--) { ++count; } printf("%d\n", count); }执行次数为：
当 N 增大时，N2N2 占主导，低阶项和常数可以忽略。因此我们只需要关注最高阶项。
2.2 大O渐进表示法
大O符号（Big O notation）用于描述函数的渐进行为。推导大O阶的方法：
- 用常数1取代运行时间中的所有加法常数。
- 只保留最高阶项。
- 如果最高阶项存在且系数不为1，则去掉系数。
例如，F(N)=N2+2N+10F(N)=N2+2N+10 的大O表示为 O(N2)O(N2)。
2.3 最好、平均、最坏情况
有些算法在不同输入下的运行时间不同。例如，在长度为N的数组中查找元素x：
- 最好情况：1次找到（第一个就是x）
- 最坏情况：N次找到（最后一个或不存在）
- 平均情况：N/2次找到
在实际中，我们通常关注最坏情况，因为它给出了算法性能的保证。所以查找算法的时间复杂度为 O(N)O(N)。
2.4 常见时间复杂度计算举例
实例1：双重循环 + 单循环
void Func2(int N) { int count = 0; for (int k = 0; k < 2 * N; ++k) { ++count; } int M = 10; while (M--) { ++count; } printf("%d\n", count); }执行次数：2N+102N+10，大O表示：O(N)
实例2：两个未知数
void Func3(int N, int M) { int count = 0; for (int k = 0; k < M; ++k) { ++count; } for (int k = 0; k < N; ++k) { ++count; } printf("%d\n", count); }执行次数：M+NM+N，大O表示：O(M+N)O(M+N)（若 M 远大于 N，可表示为 O(M)O(M)）
实例3：常数循环
void Func4(int N) { int count = 0; for (int k = 0; k < 100; ++k) { ++count; } printf("%d\n", count); }执行次数：100（常数），大O表示：O(1)O(1)
实例4：strchr 函数
const char* strchr(const char* str, int character);在字符串中查找字符，最好情况1次，最坏N次，时间复杂度 O(N)O(N)
实例5：冒泡排序
void BubbleSort(int* a, int n) { assert(a); for (size_t end = n; end > 0; --end) { int exchange = 0; for (size_t i = 1; i < end; ++i) { if (a[i-1] > a[i]) { Swap(&a[i-1], &a[i]); exchange = 1; } } if (exchange == 0) break; } }
实例6：二分查找
int BinarySearch(int* a, int n, int x) { assert(a); int begin = 0; int end = n - 1; while (begin <= end) { int mid = begin + ((end - begin) >> 1); if (a[mid] < x) begin = mid + 1; else if (a[mid] > x) end = mid - 1; else return mid; } return -1; }每次查找将区间缩小一半，最坏情况下需要 log2N次，时间复杂度 O(logN)
实例7：阶乘递归
long long Fac(size_t N) { if (0 == N) return 1; return Fac(N-1) * N; }递归调用了 N 次，每次操作常数时间，时间复杂度 O(N)
实例8：斐波那契递归
long long Fib(size_t N) { if (N < 3) return 1; return Fib(N-1) + Fib(N-2); }递归展开是一棵二叉树，节点数约为 2N，时间复杂度 O(2^N)（指数爆炸）
3. 空间复杂度
3.1 概念
空间复杂度也是一个数学表达式，它衡量算法在运行过程中临时占用存储空间的大小(其实就是判断额外创建的变量的数目）。注意，我们只关心额外开辟的空间，不包括输入数据本身占用的空间（那些已经由调用者提供）。
空间复杂度同样使用大O渐进表示法。
3.2 实例分析
实例1：冒泡排序
void BubbleSort(int* a, int n) { assert(a); for (size_t end = n; end > 0; --end) { int exchange = 0; for (size_t i = 1; i < end; ++i) { if (a[i-1] > a[i]) { Swap(&a[i-1], &a[i]); exchange = 1; } } if (exchange == 0) break; } }只使用了常数个额外变量（end、exchange、i），空间复杂度 O(1)
实例2：斐波那契数列（非递归）
long long* Fibonacci(size_t n) { if (n == 0) return NULL; long long* fibArray = (long long*)malloc((n+1) * sizeof(long long)); fibArray[0] = 0; fibArray[1] = 1; for (int i = 2; i <= n; ++i) { fibArray[i] = fibArray[i-1] + fibArray[i-2]; } return fibArray; }动态开辟了 n+1 个空间，空间复杂度 O(N)O(N)
实例3：阶乘递归
long long Fac(size_t N) { if (N == 0) return 1; return Fac(N-1) * N; }递归调用 N 次，每次调用在栈帧上开辟空间，总共需要 N 层栈帧，空间复杂度 O(N)
4. 常见复杂度对比
随着问题规模增大，不同复杂度的增长速度对比如下（假设 N=10, 100, 1000）：
| N | O(1) | O(log N) | O(N) | O(N log N) | O(N²) | O(2^N) |
|---|---|---|---|---|---|---|
| 10 | 1 | ~3 | 10 | ~30 | 100 | 1024 |
| 100 | 1 | ~7 | 100 | ~700 | 10000 | 天文数字 |
| 1000 | 1 | ~10 | 1000 | ~10000 | 10^6 | 几乎不可能 |
可见，设计低复杂度的算法至关重要。
5. 复杂度的OJ练习
5.1 消失的数字
题目：数组 nums 包含从 0 到 n 的所有整数，但缺了一个。请找出缺失的那个数。
示例：输入 [3,0,1]，输出 2
链接：LeetCode 缺失的数字
思路：
- 方法1：排序后遍历，但排序至少 O(N log N)
- 方法2：用哈希表标记，空间 O(N)
- 方法3：数学公式，先求 0~n 的和，减去数组和，得到缺失数，时间 O(N)，空间 O(1)
- 方法4：异或运算，将 0~n 与数组所有数异或，结果即为缺失数（利用 a^a=0, 0^b=b）
代码实现：
int missingNumber(int* nums, int numsSize) { int sum=0; for(int i=0;i<numsSize;i++) { sum^=i^nums[i]; } sum^=numsSize; return sum; }推荐使用方法3或4，达到 O(N) 时间、O(1) 空间。
5.2 旋转数组
题目：给定一个数组，将数组中的元素向右旋转 k 个位置。
示例：输入 [1,2,3,4,5,6,7] 和 k=3，输出 [5,6,7,1,2,3,4]
链接：LeetCode 旋转数组
思路：
- 方法1：每次旋转1个，重复 k 次，时间复杂度 O(kN)，太慢
- 方法2：使用额外数组，将原数组元素放到正确位置，时间 O(N)，空间 O(N)
- 方法3：原地翻转法（经典）：
- 反转整个数组：[7,6,5,4,3,2,1]
- 反转前 k 个：[5,6,7,4,3,2,1]
- 反转后 n-k 个：[5,6,7,1,2,3,4]
时间复杂度 O(N)，空间 O(1)
代码实现：
void reverse(int* nums,int left,int right) { while(left<right) { int tmp=nums[right]; nums[right]=nums[left]; nums[left]=tmp; left++; right--; } } void rotate(int* nums, int numsSize, int k) { k=k%numsSize; reverse(nums,0,numsSize-k-1);//翻转前n-k个数 reverse(nums,numsSize-k,numsSize-1);//翻转后k个数 reverse(nums,0,numsSize-1);//翻转整个数组 }总结
- 时间复杂度关注算法运行时间随规模增长的趋势，使用大O表示法。
- 空间复杂度关注算法额外占用的内存空间。
- 分析算法时，通常关注最坏情况，保证性能下限。
- 常见复杂度从优到劣：O(1) < O(log N) < O(N) < O(N log N) < O(N²) < O(2^N)
- 在实际开发中，要根据场景选择合适的数据结构和算法，兼顾时间与空间。
掌握复杂度分析，是编写高效代码的基础，也是面试中不可或缺的技能。接下来，我们将运用这些知识，分析更多数据结构和算法的性能。
