算法复杂度的简单介绍

本文主要是介绍算法复杂度的简单介绍，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

算法复杂度是衡量算法执行效率和资源消耗的指标，通常分为时间复杂度和空间复杂度。时间复杂度评估算法执行所需时间随输入规模的变化，空间复杂度评估算法占用内存的增长情况。复杂度通常用大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)