理解算法的时间复杂度[每日前端夜话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),其中,nlog(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/

原文发布于微信公众号 - 前端先锋(jingchengyideng)

原文发表时间:2019-06-11

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券