时间复杂度衡量算法运行快慢，空间复杂度衡量额外空间占用。核心采用大 O 渐进表示法，忽略低阶项和常数系数。常见复杂度包括常数阶 O(1)、线性阶 O(N)、平方阶 O(N^2)、对数阶 O(logN) 及递归复杂度。空间复杂度关注运行时显式申请的空间，如冒泡排序为 O(1)，数组操作可能为 O(N)。掌握复杂度分析有助于评估算法效率。
T(N) = N，和另一个算法函数式为 T(N) = N^2 比较，必然是第一个快。大 O 渐进表示法的规则：
- 时间复杂度函数式 T(N) 中，只保留最高阶项，去掉那些低阶项（当 N 无穷大时，低阶项的影响越来越小）。
- 如果最高阶项是一个一次线性函数，则去除常数系数（当 N 无穷大时，1 的影响很小）。
- T(N) 中如果没有 N 相关的项目，只有常数项，用常数 1 取代所有加法常数。
我们来判断一段代码的时间复杂度：
// 请计算一下 Func1 中++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;
}
}
Func1 执行的基本操作次数：T(N) = N^2 + 2 * N + 10
通过对 N 取值分析，对结果影响最大的一项是 N^2
通过以上方法，可以大致评估 Func1 的时间复杂度为：O(N^2)
我们想计算代码运算的时间，可以运用 clock 函数进行计算。运算过程为运算末 - 运算初。
#include <stdio.h>
#include <time.h>
int main() {
int i = 0;
int begin = clock();
int x = 10;
int n = 100; // 假设 n 有值
for(i = 0; i < n; i++) {
x++;
}
int end = clock();
// 计算运行时间
printf("%dms", end - begin);
return 0;
}
| 表达式 | 复杂度 | 阶数 |
|---|---|---|
| 5201314 | O(1) | 常数阶 |
| 3n+4 | O(n) | 线性阶 |
| 3n^2+4n+5 | O(n^2) | 平方阶 |
| 3log(2)n+4 | O(log n) | 对数阶 |
| 2n+3nlog(2)n+14 | O(n log n) | nlogn 阶 |
| n^3+2n^2+4n+6 | O(n^3) | 立方阶 |
| 2^n | O(2^n) | 指数阶 |
#include <stdio.h>
int main() {
int x = 0;
scanf("%d", &x);
printf("%d", x);
return 0;
}
执行的基本操作次数：T(N) = 3
根据推导规则第 3 条得出时间复杂度为：O(1)
// 计算 Func2 的时间复杂度？
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);
}
Func2 执行的基本操作次数：T(N) = 2N + 10
根据推导规则第 3 条得出 Func2 的时间复杂度为：O(N)
// 计算 Func3 的时间复杂度？
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);
}
Func3 执行的基本操作次数：T(N) = M + N
因此：Func3 的时间复杂度为：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("%d\n", x);
printf("%dms\n", end - begin);
return 0;
}
执行的基本操作次数：T(N) = n * n
因此：时间复杂度为：O(N^2)
void func5(int n) {
int cnt = 1;
while (cnt < n) {
cnt *= 2;
}
}
当 n=2 时，执行次数为 1
当 n=4 时，执行次数为 2
当 n=16 时，执行次数为 4
假设执行次数为 x，则 2^x = n
因此执行次数：x = log n
因此：func5 的时间复杂度取最差情况为：O(log n)
递归时间复杂度：所有递归调用次数的累加
// 计算阶乘递归 Fac 的时间复杂度？
long long Fac(size_t N) {
if (N == 0) return 1;
return Fac(N - 1) * N;
}
调用一次 Fac 函数的时间复杂度为 O(1)，而在 Fac 函数中，存在 n 次递归调用 Fac 函数 因此：阶乘递归的时间复杂度为：O(n)
我们再来看一下往递归里加个 for 循环：此时递归的时间复杂度为：O(n^2)
（此处省略具体图片展示，逻辑同单递归扩展）
空间复杂度算的是变量个数，是对一个算法在运行过程中临时占用存储空间大小的量度，同样也使用大 O 渐进表示法。(一般在编程中不考虑空间复杂度，而多用时间复杂度。空间复杂度多运用在嵌入式)
注意：函数运行时所需要的栈空间 (存储参数、局部变量、一些寄存器信息等) 在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。 我们先来看一下经典的冒泡排序。
// 计算 BubbleSort 的时间复杂度？
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;
}
}
函数栈帧在编译期间已经确定好了，只需要关注函数在运行时额外申请的空间。 BubbleSort 额外申请的空间有 exchange 等有限个局部变量，使用了常数个额外空间，因此空间复杂度为 O(1)
void reverse(int* nums, int left, int right) {
while (left < right) {
int tap = nums[left];
nums[left] = nums[right];
nums[right] = tap;
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;
}
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online