大 O 表示法
大 O 表示法是用户衡量算法效率的简化标记。
我们在分析算法效率时，会从时间和空间两种维度进行评判，根据算法输入数据的大小，使用大 O 表示它对算法时间和空间上的关系。
算法的执行时间效率称为时间复杂度，一般统计重复执行代码的次数。例如，使用 for 循环遍历一个长度为 N 的数组，使用大 O 表示法，它的时间复杂度是 O(N)，因为代码需要至少重复 N 次，才能遍历完所有数组元素：
javascript
for (let i = 0; i < arr.length; i++) {
console.log(arr[i]);
}如果算法的代码和输入的大小没关系，只执行固定次数的代码，那么它的时间复杂度为 O(1)，例如只获取数组的长度：
javascript
function getLength(arr) {
return arr.length;
}大 O 表示法是粗略的估算算法的效率，会直接忽略常数，例如我们使用平行的两个 for 循环，遍历两次数组，可能直接得出时间复杂度为 O(2N)，但是最终我们还是表示为 O(N)：
javascript
// for 1
for (let i = 0; i < arr.length; i++) {
console.log(arr[i]);
}
// for 2
for (let i = 0; i < arr.length; i++) {
console.log(arr[i]);
}对于无关输入大小，只执行固定行数的代码，无论是 1 行、5 行还是 10 行，都可以认为是 O(1)：
javascript
function getLength(arr) {
let first = arr[0];
let second = arr[1];
return first + second;
}对于算法的评价，会分为最佳情况、平均情况和最坏情况，因为有的算法会根据输入数据的不同，会有不同的时间复杂度，大 O 表示法通常表示的是最坏情况。
对于空间复杂度，大 O 表示法表示的是算法在执行时，需要额外占用的内存空间，例如对于冒泡排序，它不需要额外创建存储空间，而是就地对原数组进行排序，所以它的空间复杂度是 O(1)：
javascript
function bubbleSort(arr) {
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
}
}
}
return arr;
}常见算法的时间复杂度
下面列出一些常见算法的时间复杂度：
- 数组的访问：O(1)
- 链表的插入和删除：O(1)
- 数组的查找：O(N)
- 折半查找：O(logN)，因为每次查找都会少 N / 2 数据。
- 冒泡排序、选择排序、插入排序、快速排序：O(N2)
- 归并排序：O(NlogN)
- 有些算法的时间复杂度并不稳定，例如插入排序、快速排序等。它们会根据原始输入的数组是否已经整体有序，所表现出来的时间复杂度也不相同。例如插入排序在最好情况下的时间复杂度是 O(n)。
| 排序算法 | 平均时间复杂度 | 最坏时间复杂度 | 最好时间复杂度 | 空间复杂度 |
|---|---|---|---|---|
| 冒泡排序 | O(n^2) | O(n^2) | O(n) | O(1) |
| 选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) |
| 插入排序 | O(n^2) | O(n^2) | O(n) | O(1) |
| 快速排序 | O(nlogn) | O(n^2) | O(nlogn) | O(logn) - O(n) |
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) |
| 计数排序 | O(n + k) | O(n + k) | O(n + k) | O(n + k) |
| 桶排序 | O(n + k) | O(n^2) | O(n) | O(n + k) |
| 基数排序 | O(d(n + k)) | O(d(n + k)) | O(d(n + k)) | O(n + k) |