算法复杂度的简单介绍
算法复杂度是衡量算法执行效率和资源消耗的指标，通常分为时间复杂度和空间复杂度。时间复杂度评估算法执行所需时间随输入规模的变化，空间复杂度评估算法占用内存的增长情况。复杂度通常用大O符号来表示，它描述了最坏情况下的增长速率。
1. 时间复杂度
时间复杂度表示算法执行所需时间随输入规模 nnn 的变化关系。常见的时间复杂度如下（从快到慢）：
a. 常数时间：O(1)
- 不管输入大小如何，算法总是执行固定的操作。
- 示例：数组中访问某个元素。
int element = array[5]; // O(1)
b. 对数时间：O(log n)
- 每次迭代减少问题规模的某个倍数，通常是二分法等算法。
- 示例：二分查找。
int binarySearch(int arr[], int size, int target) {int left = 0, right = size - 1;while (left <= right) {int mid = left + (right - left) / 2;if (arr[mid] == target)return mid;else if (arr[mid] < target)left = mid + 1;elseright = mid - 1;}return -1; }
c. 线性时间：O(n)
- 算法的时间复杂度随着输入大小线性增长。
- 示例：遍历一个数组。
for (int i = 0; i < n; i++) { // O(n) }
d. 线性对数时间：O(n log n)
- 比线性复杂度稍慢，常见于高效的排序算法，如归并排序、快速排序。
- 示例：归并排序。
void mergeSort(int arr[], int n) { if (n > 1) { // Divide the array into two halves mergeSort(arr, n / 2); mergeSort(arr + n / 2, n - n / 2); // Merge the two halves } }
e. 平方时间：O(n²)
- 算法的时间复杂度随着输入规模的平方增长，常见于嵌套的循环。
- 示例：冒泡排序。
-
void bubbleSort(int arr[], int n) {for (int i = 0; i < n - 1; i++) {for (int j = 0; j < n - i - 1; j++) {if (arr[j] > arr[j + 1]) {// swap}}} }
f. 立方时间：O(n³)
- 时间复杂度与输入规模的立方成比例，通常出现在三重嵌套循环中。
- 示例：矩阵乘法的朴素算法。
g. 指数时间：O(2^n)
- 输入规模每增加1，执行时间翻倍，通常是解决组合问题的递归算法。
- 示例：递归解决斐波那契数列。
int fibonacci(int n) {if (n <= 1) return n;return fibonacci(n - 1) + fibonacci(n - 2); // O(2^n) }
h. 阶乘时间：O(n!)
- 输入规模每增加1，执行时间呈阶乘增长，常见于排列组合问题。
- 示例：解决N皇后问题。
2. 空间复杂度
空间复杂度评估算法所需的内存随输入规模的变化情况。它表示程序在运行过程中需要的额外存储空间。
- O(1)：常数空间，不管输入规模如何，所需额外空间是固定的。例如，交换两个变量的算法。
- O(n)：线性空间，所需的额外空间随着输入规模线性增加。例如，使用一个数组存储输入数据的副本。
- O(n²)：所需的存储空间与输入的平方成正比，通常出现在矩阵相关的问题中。
3. 常见算法的时间复杂度表
| 算法类型 | 最佳情况 | 平均情况 | 最坏情况 |
|---|---|---|---|
| 冒泡排序 | O(n) | O(n²) | O(n²) |
| 选择排序 | O(n²) | O(n²) | O(n²) |
| 插入排序 | O(n) | O(n²) | O(n²) |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) |
| 快速排序 | O(n log n) | O(n log n) | O(n²) |
| 二分查找 | O(1) | O(log n) | O(log n) |
| 线性查找 | O(1) | O(n) | O(n) |
4. 大O符号的简化原则
在表示时间复杂度时，我们通常关注输入规模 nnn 增长时的趋势，因此忽略常数项和低次项。例如：
- 如果一个算法的复杂度是 5n+35n + 35n+3，我们会简化为 O(n)O(n)O(n)。
- 如果复杂度是 n2+nn^2 + nn2+n，我们会简化为 O(n2)O(n^2)O(n2)。
5. 实际应用中的复杂度权衡
虽然理论上高效的算法（如 O(n log n) 的排序算法）往往表现优异，但在某些场景下，低复杂度的算法未必比高复杂度的算法快。例如，当输入规模较小时，冒泡排序（O(n²)）可能比快速排序（O(n log n)）更快。因此，选择算法时需要考虑实际数据规模和硬件环境。
6. 总结
- 时间复杂度衡量算法执行时间随输入规模的增长而变化。
- 空间复杂度评估算法所需的存储空间随输入规模的变化。
- 常见的时间复杂度包括：O(1), O(log n), O(n), O(n log n), O(n²) 等，越高阶的复杂度，随着输入规模增长，算法性能下降越快。
- 编写高效算法时应考虑优化时间和空间复杂度，在不同的场景中合理选择算法。