时间复杂度与空间复杂度
评估一个算法的优劣,核心在于两个维度:时间和空间。时间复杂度衡量算法运行的快慢,空间复杂度则关注运行过程中额外占用的存储空间。
一、时间复杂度基础
算法的时间复杂度通常表示为函数 T(N),代表基本操作的执行次数。需要注意的是,不同编译器编译所需时间会有差异,新编译器通常更快,但这不影响我们分析算法本身的逻辑效率。
比较 T(N) = N 和 T(N) = N^2 时,显然前者在数据量增大时表现更优。
大 O 渐进表示法
为了简化分析,我们遵循以下规则推导大 O 阶:
- 保留最高阶项:当 N 趋于无穷大时,低阶项影响微乎其微,直接忽略。
- 去除常数系数:如果最高阶项是线性函数(如 5N),去掉系数 5,只保留 N。
- 常数项归一:如果没有 N 相关项,仅含常数,统一用 1 取代。
示例分析
void Func1(int N) {
int count = 0;
// 嵌套循环,执行 N*N 次
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
++count;
}
}
// 线性循环,执行 2*N 次
for (int k = 0; k < 2 * N; ++k) {
++count;
}
// 常数循环,执行 10 次
int M = 10;
while (M--) {
++count;
}
}
Func1 的基本操作次数为 T(N) = N² + 2N + 10。根据规则,保留最高阶项 N²,因此时间复杂度为 O(N²)。
常见复杂度对比
| 表达式 | 大 O 表示 | 类型 |
|---|---|---|
| 5201314 | O(1) | 常数阶 |
| 3n+4 | O(n) | 线性阶 |
| 3n²+4n+5 | O(n²) | 平方阶 |
| 3log₂n+4 | O(log n) | 对数阶 |
| 2ⁿ | O(2ⁿ) | 指数阶 |
二、典型场景解析
1. 常数阶 O(1)
无论输入规模如何,操作次数固定。
#include<stdio.h>
int main() {
int x = 0;
scanf("%d", &x); // 修正了原稿拼写错误 scnaf -> scanf
printf("%d", x);
return 0;
}
执行次数恒定为 3 次,复杂度 O(1)。
2. 线性阶 O(N)
操作次数随 N 线性增长。
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 + 10,去低阶和系数后为 O(N)。
若存在两个独立变量 M 和 N:
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 + N。若 M 和 N 同阶,则为 O(N);若差异巨大,则取较大者。
3. 平方阶 O(N²)
嵌套循环的典型特征。
#include<stdio.h>
int main() {
int x = 0;
int begin = clock();
int n = 100000;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
x++;
}
}
int end = clock();
printf("%dms\n", end - begin);
return 0;
}
注意:此处需包含 <time.h> 头文件才能使用 clock()。双重循环导致复杂度为 O(N²)。
4. 对数阶 O(log N)
每次迭代将问题规模减半。
void func5(int n) {
int cnt = 1;
while (cnt < n) {
cnt *= 2;
}
}
设执行次数为 x,则 2^x = n,解得 x = log₂n。最坏情况复杂度为 O(log₂n)。
5. 递归函数
递归的时间复杂度取决于调用次数与单次调用的开销。
单递归示例:
long long Fac(size_t N) {
if (N == 0) return 1; // 修正了原稿逻辑错误,增加基准条件
return Fac(N-1) * N;
}
每次调用耗时 O(1),共调用 N 次,总复杂度 O(N)。
双递归示例:
若递归内部包含循环或多次递归调用,复杂度会显著上升。例如斐波那契数列的朴素递归实现,其时间复杂度接近 O(2^N),因为存在大量重复计算。
三、空间复杂度
空间复杂度衡量算法运行时临时占用的存储空间大小,同样使用大 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)
void reverse(int* nums, int left, int right) {
while (left < right) {
int temp = nums[left]; // 修正变量名 tap -> temp
nums[left] = nums[right];
nums[right] = temp;
left++;
right--;
}
}
int main() {
int nums[] = { 1,2,3,4,5,6,7 };
int numsSize = sizeof(nums) / sizeof(nums[0]);
int k = 0;
scanf("%d", &k);
k %= numsSize;
reverse(nums, 0, numsSize - k - 1);
reverse(nums, numsSize - k, numsSize - 1);
reverse(nums, 0, numsSize - 1);
for (int i = 0; i < numsSize; i++) {
printf("%d ", nums[i]);
}
return 0;
}
此例中虽然创建了数组,但这是输入数据本身。若算法内部需要创建与 N 等大的辅助数组,空间复杂度则为 O(N)。通常情况下,空间复杂度多为 O(1)、O(N) 或 O(N²),实际优化时仍以时间复杂度为首要考量。

