大 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 表示法，你学会了吗？如果有帮助请三连并关注，想学更多的开发知识，可以在评论区留言，感谢观看！