乐趣区

理解算法的时间复杂度

jiezi

翻译：疯狂的技术宅

原文：https://www.freecodecamp.org/…

未经允许严禁转载

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Big O 表示法

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

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

当我们分析算法时，一般使用 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 天。这是一个显著的差异。这就是为什么在涉及如此大的数据量时，研究时间复杂性是非常重要的原因。

本文首发微信公众号：前端先锋

欢迎扫描二维码关注公众号，每天都给你推送新鲜的前端技术文章

欢迎继续阅读本专栏其它高赞文章：

  • 深入理解 Shadow DOM v1
  • 一步步教你用 WebVR 实现虚拟现实游戏
  • 13 个帮你提高开发效率的现代 CSS 框架
  • 快速上手 BootstrapVue
  • JavaScript 引擎是如何工作的？从调用栈到 Promise 你需要知道的一切
  • WebSocket 实战：在 Node 和 React 之间进行实时通信
  • 关于 Git 的 20 个面试题
  • 深入解析 Node.js 的 console.log
  • Node.js 究竟是什么？
  • 30 分钟用 Node.js 构建一个 API 服务器
  • Javascript 的对象拷贝
  • 程序员 30 岁前月薪达不到 30K，该何去何从
  • 14 个最好的 JavaScript 数据可视化库
  • 8 个给前端的顶级 VS Code 扩展插件
  • Node.js 多线程完全指南
  • 把 HTML 转成 PDF 的 4 个方案及实现
  • 更多文章 …
退出移动版