时间复杂度与空间复杂度
评估一个算法的好坏，核心在于对比其时间和空间两个维度。时间复杂度主要衡量算法运行的快慢，而空间复杂度则关注运行过程中需要的额外存储空间。
大 O 渐进表示法
算法的时间复杂度通常用函数 T(N) 表示，代表基本操作的执行次数。在分析时，我们遵循大 O 渐进表示法的规则：
- 只保留最高阶项，忽略低阶项（当 N 趋于无穷大时）。
- 如果最高阶项是线性函数，去除常数系数。
- 如果没有 N 相关项，仅保留常数 1。
来看一段代码示例：
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;
}
}
这里的基本操作次数 T(N) = N² + 2N + 10。随着 N 增大，N² 的影响占主导，因此时间复杂度为 O(N²)。
实际运行时间测试
虽然理论推导很重要，但有时我们也想实测代码耗时。可以使用 clock() 函数记录运算前后的时间点。注意头文件需要包含 <time.h>。
#include <stdio.h>
#include <time.h>
int main() {
int i = 0;
clock_t begin = clock();
int x = 10;
int n = 100000; // 定义 n 以便循环
for(i = 0; i < n; i++) {
x++;
}
clock_t end = clock();
printf("%dms\n", (int)((end - begin) / (double)CLOCKS_PER_SEC * 1000));
return 0;
}
常见复杂度对比
| 表达式 | 复杂度 | 说明 |
|---|---|---|
| 5201314 | O(1) | 常数阶 |
| 3n+4 | O(n) | 线性阶 |
| 3n^2+4n+5 | O(n^2) | 平方阶 |
| log₂n | O(log n) | 对数阶 |
| nlog₂n | O(n log n) | nlogn 阶 |
| n^3 | O(n^3) | 立方阶 |
| 2^n | O(2^n) | 指数阶 |
常数阶 O(1)
int main() {
int x = 0;
scanf("%d", &x);
printf("%d", x);
return 0;
}
无论输入如何，操作次数固定，复杂度为 O(1)。
线性阶 O(N)
例如 Func2 中，循环次数与 N 成正比，忽略常数项后为 O(N)。如果是两个独立循环分别依赖 M 和 N，且 M 与 N 无关，则复杂度为 O(M+N)，通常简化为 O(N)。
平方阶 O(N^2)
嵌套循环是典型的平方阶结构。内层循环每执行一次外层就执行一次，总次数约为 N*N。
对数阶 O(log N)
void func5(int n) {
int cnt = 1;
while (cnt < n) {
cnt *= 2;
}
}
每次迭代数值翻倍，执行次数 x 满足 2^x = n，即 x = log₂n。
递归函数
递归的时间复杂度是所有递归调用次数的累加。 单递归如阶乘，调用深度为 N，每次操作 O(1)，总复杂度 O(N)。 若递归内部包含循环，复杂度会相应增加，例如 O(N^2)。
空间复杂度
空间复杂度衡量的是临时占用存储空间的大小，同样使用大 O 表示法。一般编程中更关注时间复杂度，但在嵌入式开发中空间限制较严。
注意：函数栈帧（参数、局部变量）通常在编译期确定，空间复杂度主要看运行时显式申请的额外空间。
冒泡排序 O(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;
}
}
除了几个局部变量外没有申请额外数组，空间复杂度为 O(1)。
三个反置 O(N)
如果涉及创建新数组或动态分配内存，空间复杂度通常为 O(N)。例如反转数组的操作，若原地修改则为 O(1)，若需辅助数组则为 O(N)。
总的来说，在复杂度分析中，时间复杂度通常是首要考量指标。
