你有没有想过为什么你写的程序要花这么长时间才能运行？也许您想知道是否可以提高代码的效率。了解代码运行如何将代码提升到下一个级别。Big-O表示法是计算代码实际效率的一个方便工具。

什么是大o符号(big-o notation)？

Big-O表示法提供了一种计算运行代码所需时间的方法。您可以实际计算代码运行所需的时间，但是使用这种方法，很难捕捉到小的时间差异。例如，运行20到50行代码所需的时间非常少。然而，在一个大型项目中，这些低效率可能会累积起来。

Big-O表示法计算一个算法必须执行多少步才能衡量其效率。如果需要调整代码以提高效率，那么以这种方式处理代码是非常有效的。Big-O表示法将使您能够根据运行所需的步骤数来度量不同的算法，并客观地比较算法的效率。

如何计算big-o符号

让我们考虑两个函数来计算一个抽屉中有多少只袜子。每个函数获取袜子对的数量并返回单个袜子的数量。代码是用Python编写的，但这并不影响我们计算步骤数的方式。

算法1：

算法2：

这是一个愚蠢的例子，你应该能够很容易地判断哪种算法更有效。但是为了练习，让我们把每一个都讲一遍。

相关：什么是编程中的函数？

算法1有很多步骤：

1. 它为变量individualSocks赋值为零。
2. 它给变量i赋值为1。
3. 它将i的值与numberOfPairs进行比较。
4. 它增加了两个单独的袜子。
5. 它将个人袜子的增值分配给自己。
6. 它使i增加1。
7. 然后，它在步骤3到6之间循环，循环次数与（individualsocks-1）相同。

对于算法1，我们必须完成的步骤数可以表示为：

有四个步骤，我们必须完成n次。在这种情况下，n等于numberOfPairs的值。还有两个步骤一次完成。

相比之下，算法2只有一个步骤。numberOfPairs的值乘以2。我们可以这样说：

如果还不明显的话，我们现在可以很容易地看到算法2的效率提高了很多。

大o分析

通常，当您对算法的Big-O表示法感兴趣时，您对整体效率更感兴趣，而对步长的细粒度分析则不太感兴趣。为了简化表示法，我们可以只说明效率的大小。

在上述示例中，算法2将表示为：

但算法1将简化为：

这个快速快照告诉我们算法一的效率是如何与n的值联系在一起的。数量越大，算法需要完成的步骤就越多。

线性码

因为我们不知道n的值，所以考虑n的值如何影响需要运行的代码量更有帮助。在算法1中，我们可以说这种关系是线性的。如果你画出步数和n的值，你会得到一条上升的直线。

二次码

并不是所有的关系都像线性例子那么简单。假设您有一个二维数组，并且希望在数组中搜索一个值。您可以创建如下算法：

在本例中，步骤的数量取决于ArraySearchd中的数组数量和每个数组中的值数。因此，简化的步骤数将为n*n或n²。

这个关系是一个二次关系，这意味着我们算法中的步数随着n呈指数增长。用Big-O表示法，你可以这样写：

相关：用于检查、清理和优化CSS文件的有用工具

对数码

虽然还有很多其他的关系，但我们最后要讨论的是对数关系。要刷新内存，一个数字的对数是达到给定基数的数字所需的指数值。例如：

对数等于3，因为如果我们的基数是2，我们需要一个指数值3才能得到数字8。

所以，对数函数的关系和指数函数的关系是相反的。随着n的增加，运行算法所需的新步骤也会减少。

乍一看，这似乎违反直觉。一个算法的步长怎么会比n增长慢呢？二进制搜索就是一个很好的例子。让我们考虑一个算法来搜索唯一值数组中的数字。

• 我们将从一个从最小到最大的数组开始搜索。
• 接下来，我们将检查数组中间的值。
• 如果您的号码较高，我们将在搜索中排除较低的号码，如果号码较低，我们将排除较高的号码。
• 现在，我们来看看剩余数字的中间数字。
• 同样，我们将根据目标值是高于还是低于中间值来排除一半的数字。
• 我们将继续这个过程，直到我们找到我们的目标，或确定它不在名单上。

正如您所看到的，由于二进制搜索每次都会消除一半的可能值，随着n变大，对检查数组次数的影响几乎没有影响。为了用Big-O表示法来表示这一点，我们要写：

big-o符号的重要性

Big-O nation为您提供了一种快速简便的方法来传达算法的效率。这样就更容易在不同的算法之间做出决定。如果您使用的是库中的算法，并且不一定知道代码的样子，那么这将非常有用。

当你第一次学习编码时，你从线性函数开始。从上面的图表中可以看出，这会让你走得更远。但是当你变得更有经验并且开始构建更复杂的代码时，效率开始成为一个问题。了解如何量化代码的效率将为您提供所需的工具，以开始调整代码的效率并权衡算法的优缺点。