跳到主要内容位置

大 O 表示法

大 O 表示法是用户衡量算法效率的简化标记。

我们在分析算法效率时,会从时间和空间两种维度进行评判,根据算法输入数据的大小,使用大 O 表示它对算法时间和空间上的关系。

算法的执行时间效率称为时间复杂度,一般统计重复执行代码的次数。例如,使用 for 循环遍历一个长度为 N 的数组,使用大 O 表示法,它的时间复杂度是 O(N),因为代码需要至少重复 N 次,才能遍历完所有数组元素:

for (let i = 0; i < arr.length; i++) {
console.log(arr[i]);
}

如果算法的代码和输入的大小没关系,只执行固定次数的代码,那么它的时间复杂度为 O(1),例如只获取数组的长度:

function getLength(arr) {
return arr.length;
}

大 O 表示法是粗略的估算算法的效率,会直接忽略常数,例如我们使用平行的两个 for 循环,遍历两次数组,可能直接得出时间复杂度为 O(2N),但是最终我们还是表示为 O(N):

// 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):

function getLength(arr) {
let first = arr[0];
let second = arr[1];
return first + second;
}

对于算法的评价,会分为最佳情况、平均情况和最坏情况,因为有的算法会根据输入数据的不同,会有不同的时间复杂度,大 O 表示法通常表示的是最坏情况。

对于空间复杂度,大 O 表示法表示的是算法在执行时,需要额外占用的内存空间,例如对于冒泡排序,它不需要额外创建存储空间,而是就地对原数组进行排序,所以它的空间复杂度是 O(1):

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)。

小结

好了,这个就是 2 分钟了解算法中的大 O 表示法,你学会了吗?如果有帮助请三连并关注,想学更多的开发知识,可以在评论区留言,感谢观看!