一、什么是复杂度？
1.1 为什么需要复杂度分析？
假设你写了两个程序来解决同一个问题，如何判断哪个程序更好？我们不能只看运行时间，因为：
- 不同电脑性能不同
- 同一电脑在不同时刻状态也不同
- 数据规模不同，结果也不同
所以我们需要一个客观的标准来衡量算法的效率，这就是复杂度分析。
1.2 两种复杂度
- 时间复杂度：程序运行需要多少时间（执行多少步骤）
- 空间复杂度：程序运行需要多少额外内存
二、时间复杂度基础
2.1 什么是时间复杂度？
时间复杂度描述的是随着输入规模n的增长，程序执行时间的增长趋势。
让我们看一个最简单的例子：
// 例子1：打印一个数字
void print_once(int n) {printf("%d\n", n); // 执行1次
}
无论n是多少，这个函数都只执行1次打印操作。
// 例子2：打印n次
void print_n_times(int n) {for (int i = 0; i < n; i++) {printf("%d ", i); // 执行n次}
}
这个函数会执行n次打印操作。
2.2 大O表示法
我们用大O表示法来描述时间复杂度：
- O(1) - 常数时间
- O(n) - 线性时间
- O(n²) - 平方时间
- O(log n) - 对数时间
- …
上面的例子1是O(1)，例子2是O(n)。
2.3 如何计算时间复杂度？
步骤1：计算每行代码的执行次数
void example(int n) {int sum = 0; // 执行1次for (int i = 0; i < n; i++) {sum += i; // 执行n次}printf("%d", sum); // 执行1次
}
// 总执行次数：1 + n + 1 = n + 2
步骤2：保留最高次项，忽略常数
- n + 2 → O(n)
- 3n² + 2n + 1 → O(n²)
- 5n³ + 100n → O(n³)
三、常见时间复杂度详解
3.1 O(1) - 常数时间复杂度
// 无论数组多大，都只访问一个元素
int get_first(int arr[], int n) {return arr[0]; // O(1)
}// 简单的数学运算
int calculate(int a, int b) {int sum = a + b; // O(1)int product = a * b; // O(1)return sum + product; // O(1)
} // 总体：O(1)
3.2 O(n) - 线性时间复杂度
// 遍历数组一次
int find_max(int arr[], int n) {int max = arr[0]; // O(1)for (int i = 1; i < n; i++) { // 循环n-1次if (arr[i] > max) { // O(1)max = arr[i]; // O(1)}}return max; // O(1)
} // 总体：O(n)
3.3 O(n²) - 平方时间复杂度
// 双重循环 - 冒泡排序
void bubble_sort(int arr[], int n) {for (int i = 0; i < n - 1; i++) { // 外循环：n-1次for (int j = 0; j < n - i - 1; j++) { // 内循环：平均n/2次if (arr[j] > arr[j + 1]) {// 交换int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}
} // 总体：O(n²)
3.4 O(log n) - 对数时间复杂度
// 二分查找（数组必须有序）
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(log n)
为什么是O(log n)？因为每次循环都将搜索范围减半：
- n → n/2 → n/4 → … → 1
- 需要log₂n次才能将n减到1
四、空间复杂度
4.1 什么是空间复杂度？
空间复杂度描述的是程序运行过程中需要的额外内存空间。
注意：
- 输入数据占用的空间不算
- 只计算额外申请的空间
4.2 空间复杂度示例
// O(1) 空间复杂度 - 只用了固定的几个变量
int sum_array(int arr[], int n) {int sum = 0; // 额外空间：1个intfor (int i = 0; i < n; i++) {sum += arr[i];}return sum;
}// O(n) 空间复杂度 - 创建了新数组
int* copy_array(int arr[], int n) {int* new_arr = (int*)malloc(n * sizeof(int)); // 额外空间：n个intfor (int i = 0; i < n; i++) {new_arr[i] = arr[i];}return new_arr;
}// O(n) 空间复杂度 - 递归调用
int factorial(int n) {if (n <= 1) return 1;return n * factorial(n - 1); // 递归调用栈：O(n)
}
五、复杂度分析实战
5.1 分析技巧
-
看循环：
- 单层循环通常是O(n)
- 双层嵌套循环通常是O(n²)
- 三层嵌套循环通常是O(n³)
-
看递归：
- 递归深度 × 每层的工作量
-
看数据结构：
- 数组访问：O(1)
- 链表查找：O(n)
5.2 综合例子
// 分析这个函数的时间和空间复杂度
void process_matrix(int n) {// 创建二维数组 - 空间：O(n²)int** matrix = (int**)malloc(n * sizeof(int*));for (int i = 0; i < n; i++) {matrix[i] = (int*)malloc(n * sizeof(int));}// 初始化 - 时间：O(n²)for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {matrix[i][j] = i + j;}}// 查找最大值 - 时间：O(n²)int max = matrix[0][0];for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (matrix[i][j] > max) {max = matrix[i][j];}}}// 释放内存for (int i = 0; i < n; i++) {free(matrix[i]);}free(matrix);
}
// 时间复杂度：O(n²) + O(n²) = O(n²)
// 空间复杂度：O(n²)
六、复杂度比较
当n很大时，不同复杂度的差异：
| n值 | O(1) | O(log n) | O(n) | O(n log n) | O(n²) | O(2ⁿ) |
|---|---|---|---|---|---|---|
| 10 | 1 | 3 | 10 | 33 | 100 | 1,024 |
| 100 | 1 | 7 | 100 | 664 | 10,000 | 1.27×10³⁰ |
| 1000 | 1 | 10 | 1000 | 9,966 | 1,000,000 | 1.07×10³⁰¹ |
效率排序：O(1) > O(log n) > O(n) > O(n log n) > O(n²) > O(2ⁿ)
七、实践建议
-
先写对，再优化：先确保程序正确，然后考虑效率
-
空间换时间：有时可以用更多内存来加快速度
-
选择合适的数据结构：不同数据结构有不同的复杂度特性
-
注意最坏情况：算法分析通常考虑最坏情况
小结
- 时间复杂度关注执行步数随输入规模的增长趋势
- 空间复杂度关注额外内存使用随输入规模的增长趋势
- 使用大O表示法，只保留最高次项
- 通过数循环层数可以快速估算复杂度
