理解算法的时间复杂度[每日前端夜话0x82]

每日前端夜话0x82

每日前端夜话，陪你聊前端。

每天晚上18:00准时推送。

正文共：4126 字

预计阅读时间： 11 分钟

翻译：疯狂的技术宅

来源：logrocket

理解算法的时间复杂度

在计算机科学中，算法分析是非常关键的部分。找到解决问题的最有效算法非常重要。可能会有许多算法能够解决问题，但这里的挑战是选择最有效的算法。现在关键是假如我们有一套不同的算法，应该如何识别最有效的算法呢？在这里算法的空间和时间复杂度的概念出现了。空间和时间复杂度是算法的测量尺度。我们根据它们的空间（内存量）和时间复杂度（操作次数）来对算法进行比较。

算法在执行时使用的计算机内存总量是该算法的空间复杂度（为了使本文更简短一些我们不会讨论空间复杂度）。因此，时间复杂度是算法为完成其任务而执行的操作次数（考虑到每个操作花费相同的时间）。在时间复杂度方面，以较少的操作次数执行任务的算法被认为是有效的算法。但是空间和时间复杂性也受操作系统、硬件等因素的影响，不过现在不考虑它们。

我们将通过解决一个特定问题的例子来帮你理解时间复杂度，

这个问题是搜索。我们必须在数组中查找一个元素（在这个问题中，假设数组已经按升序排序）。为了解决这个问题，我们有两种算法：

1. 线性搜索
2. 二分搜索

假设数组包含十个元素，要求我们在数组中找到数字 10。

1const array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
2const search_digit = 10;

线性搜索算法会将数组的每个元素与 search_digit 进行比较，当它在数组中找到 search_digit 时，会返回 true。现在让我们计算它执行的操作次数。这里的答案是10（因为它比较了数组的每个元素）。因此线性搜索使用十个操作来查找给定元素（这是使用线性搜索算法时对此数组的最大操作数，这也被称为最坏情况。通常线性搜索在最坏的情况下会进行 n 次操作（其中 n 是数组的大小）。

让我们来看看同样情况下的二分搜索算法。

通过此图可以轻松理解二进制搜索：

资料来源：Learneroo

如果要在这个问题上应用此逻辑，那么首先我们将 search_digit 与数组的中间元素进行比较，即 5。现在，因为 5 小于 10，那么我们将开始在大于 5 的数组元素中寻找 search_digit ，不断执行相同的操作直到我们找到所需的元素 10 为止。

现在试着计算使用二分搜索找到所需的元素进行的操作次数：大约需要四次操作。这是二分搜索的最坏情况。这表明，执行的操作数和数组的总大小之间存在对数关系。

操作次数 = log(10) = 4（约）

我们可以将此结果推广到二分搜索： 对于大小为 n 的数组，二分搜索执行的操作数为：log(n)

Big O表示法

在上面的陈述中，我们看到对于大小为 n 的数组，线性搜索将执行 n 次操作来完成查找，而二分搜索执行 log(n) 次操作（两者都是最糟糕的情况）。我们可以将其表示为图形（x轴：元素数量，y轴：操作次数）。

资料来源：Techtud

从图中可以清楚地看出，线性搜索时间复杂度的增长速度比二分搜索快得多。

当我们分析算法时，一般使用 Big O 表示法来表示其时间复杂度。

例如：线性搜索的时间复杂度可以表示为 O(n) ，二分搜索表示为 O(log n)，其中，n 和 log(n) 是执行的操作次数。

下面列出了一些流行算法的时间复杂度或大O符号：

1. 二分搜索： O(log n)
2. 线性搜索： O(n)
3. 快速排序： O(n*log n)
4. 选择排序：O(n*n)
5. 旅行商问题：O(n!)

结论

如果你读到了这里，我非常感谢。现在，必须要理解时间复杂性为何如此重要？我们知道，对于少量元素来说（比如说10），二元搜索和线性搜索所执行的操作次数之间的差异并不大，但在现实世界中的大多数时候，我们处理的是大块数据的问题。加入我们有40亿个元素要搜索，那么在最坏的情况下，线性搜索将需要40亿次操作才能完成任务，而二分搜索只需要32次操作就能完成。它们之间的区别是非常巨大的。假设如果一个操作需要1毫秒才能完成，那么二进制搜索将只需要32毫秒，而线性搜索将花费40亿毫秒，也就是大约46天。这是一个显著的差异。这就是为什么在涉及如此大的数据量时，研究时间复杂性是非常重要的原因。

原文：https://www.freecodecamp.org/news/time-complexity-of-algorithms/