什么是大 O 符号？

有没有比大 O 符号更可怕的计算机科学主题？别被它的名字吓到，大 O 符号其实没什么大不了的。它很容易理解，你不需要是数学高手就能理解。在本教程中，你将学习大 O 符号的基础知识，从常数和线性时间复杂度开始，并结合 JavaScript 中的示例进行讲解。

注意：亚马逊链接是附属的。

这是大 O 符号系列文章的第一篇。如果你想随时了解最新动态，请订阅我的每周简报“解决方案”。

大 O 符号解决了什么问题？

• 大 O 符号帮助我们回答这个问题：“它会扩展吗？”

• Big O 符号为我们提供了一种与其他开发人员（和数学家！）讨论性能的共享语言。

什么是大 O 符号？

大 O 是一种用于衡量算法性能的符号。大 O 符号从数学上描述了算法在时间和空间方面的复杂度。我们不会用秒（或分钟！）来衡量算法的速度。我们用完成算法所需的操作数量来衡量算法的增长率。

O 是“数量级”（Order of amplitude）的缩写。所以，如果我们讨论一个复杂度为O(n)的算法，我们说它的数量级，或者说增长率，是n，也就是线性复杂度。

你可能会读到或听到“大 O”被称为渐近运行时间，或渐近计算复杂度。这是一种描述函数极限的奇特方式。数学中有一个分支，即序理论，专门研究这个主题。就我们的目的和意图而言，序：

... 提供了一个正式的框架来描述诸如“这小于那”或“这先于那”之类的陈述。

我们使用顺序来评估算法的复杂性。

数学钟🧮🕐

您不需要是数学天才就能理解 Big O，但我们需要介绍一些基本概念，以帮助您的成功。

如果您还记得代数，您使用过诸如f(x)和g(x)之类的函数，甚至做过诸如f(g(x))之类的事情，其中​​ f()和g()是方程，而x是传递给函数的数值（或另一个方程！）。

当我们编程时，我们给“方程式”起描述性的名称（至少我希望你这样做），例如isAuthenticated和calcuateMedian，但我们也可以将它们命名f为和g（请不要）。

假设f(x)等于3x ² + 12x - 6。

我们可以说f(x)的数量级，或者说增长率是O(n² ⁾。我们稍后会解释原因。

更常见的是简单地说“ f (x)是 n 2 的阶^”，或者“ f (x)是 n 2 的大 O ^”。

数学时间结束。

就目前而言。😀

大 O 符号如何工作？

大 O 符号衡量最坏情况的运行时间。

为什么？

因为我们不知道我们不知道什么。

如果我们编写搜索算法，我们并不总是能提前知道查询结果。如果我们编写排序算法，我们并不总是能提前知道数据集。如果查询结果恰好是最后一个元素，或者数据集非常混乱，该怎么办？我们想知道我们的算法性能到底有多差。

最坏情况也被称为“上限”。又是极限！

你会遇到很多像这样的表格：

这列出了从最快到最慢的常见运行时间。

我们接下来会多次参考这一点。

在进入任何代码之前，让我们先亲手感受一下 Big O（双关语）。我们将使用Grokking Algorithms中的一个例子。

假设我给你一张正方形纸，让你把它分成16个方格。你会如何解决这个问题？

你可以采用蛮力法，画出十六个独立的正方形。如果采用这种方法，需要执行多少个步骤或计算？

十六。

有没有更简单的方法？当然！

把纸对折，然后再对折。四个正方形！

现在再将其对折两次。

当你将它展开时，纸张将被分成十六个方格。

需要多少步骤或计算？

四。

用大 O 表示法来说，我们的第一种方法，即蛮力法，是 O(n)，即线性时间。创建 16 个正方形需要 16 步运算。但我们的第二种方法，经过重构和优化，是 O(log n)，即对数时间（指数运算的倒数）。创建 16 个正方形仅需四步。

我们稍后会讨论 O(log n)。我们先从 O(1) 开始，这有助于我们理解 O(n)。

O(1)：恒定时间复杂度

假设您正在使用一个在数组中返回用户全名的 API，如下所示：

[“Jared”, “Nielsen”];

你的任务是获取用户的名字。很简单，用 JavaScript 实现：

const getFirstName = data => {
    return data[0];
}

无论你运行你的“算法”多少次，它只需执行一次运算即可返回所需值。这就是 O(1)，即常数时间。

这是另一个 JavaScript 示例：

const isEven = num => num % 2 === 0;

我们的算法检查一个数字是奇数还是偶数，并相应地返回 true 或 false。它只需执行一次运算。同样，时间复杂度为 O(1)。

什么是大 O 符号？

大 O 符号其实并不难理解。它非常容易理解，你不需要数学天赋就能理解。在本教程中，你学习了大 O 符号的基础知识，并通过 JavaScript 示例了解了常数和线性时间复杂度。

敬请关注大 O 符号系列的第二部分，我们将探讨 O(n)，即线性时间复杂度。如果您想随时了解最新动态，请订阅我的每周简报“解决方案”。