大 O 符号入门指南

作为一名没有计算机科学背景的开发者，为了提升我的算法技能，大 O 符号是我必须加倍努力学习的概念之一。在本文中，我将介绍一些使用 JavaScript 实现大 O 符号的基础知识。

什么是大 O 符号？

大 O 符号用于描述函数运行所需的时间，并允许我们正式讨论运行时间如何随着输入的增长而增长。它具体描述了运行时间方面的最坏情况。

大 O 表示为 O( n )，其中n是输入的大小。
我们将研究三个具体的表达式：O(1)、O( n ) 和 O( n² )。

在确定运行算法所需的时间时，我们有一些有用的经验法则：

1. 在考虑大 O 时，我们只关心最广义的视角。我们关注的是当n变得非常大时会发生什么。在这种情况下，加 100 或乘以 5 的显著效果就会减弱。

2. 常数并不重要：

• 如果我们有 O(5 n )，则简化为 O( n )
• 如果 O(42) 则简化为 O(1)
• 如果我们有 O(10 n² )，则简化为 O( n² )

O(1)

这个表达式的意思是，一个函数的运行时间是常数。无论输入是 1 还是 1000，随着输入的增长，运行时间的消耗保持不变。

例如：

function logAtMostFive(n) {
  for (let i = 1; i <= Math.min(5, n); i++) {
    console.log(i)
  }
}

在上面的函数中，无论n是多少，运行时间都将保持不变。因此，如果你运行这个函数，你会注意到，无论你传入5还是200，日志都只会是1, 2, 3, 4, 5。

因此，我们可以说这个函数的大 O 符号是 O(1)。

在）​

这个表达式的意思是，它所花费的时间与n的大小呈线性关系。运行时间会随着输入的增加而增加。

例如：

function logAtLeastFive(n) {
  for (let i = 1; i <= Math.max(5, n); i++) {
    console.log(i)
  }
}

在上面的函数中，我们看到了与上一个示例相反的效果。随着n 的增加，运行时间相对于n增加。运行此函数时，您会注意到，如果传入5日志，则为1, 2, 3, 4, 5；如果传入200日志，则为1, 2, 3, 4, 5, 6, 7...200

因此，我们可以说这个函数的大 O 符号是 O( n )。

O( n² )

这个表达式意味着算法的运行时间与n的平方成正比。时间会随着输入的增加而呈指数增长。这在涉及嵌套迭代的函数中很常见。更深的嵌套会导致 O( n³ )、O( n⁴ ) 等复杂度。

例如：

function printAllPairs(n) {
  for (var i = 0; i <= n; i++) {
    for (var j = 0; j <= n; j++) {
      console.log(i, j);
    }
  }
}

在上面的函数中，随着n 的增加，运行时间呈指数增长。如前所述，当n的大小变得非常大时，这会严重影响性能。

因此，我们可以说这个函数的大 O 符号是 O( n² )。

结论

大 O 符号使我们能够描述算法运行所需的时间。随着应用程序的增长以及处理的数据量或大小的增长，我们的函数处理这些信息的方式变得至关重要。

希望您喜欢这份 Big O 入门指南！

动图