原标题：算法的时空复杂度简介

来源：AI 研习社        链接：https://www.yanxishe.com/TextTranslation/1813

在计算机科学中，算法分析是至关重要的一部分。找到最有效的算法来解决问题是非常重要的。解决一个问题可能有多种算法，但选择出最有效的一个是个难题。  

现在的问题是，如果我们有一组不同的算法，我们如何识别出最有效的算法？由此，算法的时空复杂性的概念应运而生。空间和时间复杂度是算法的一种度量尺度。我们根据算法的空间(内存)和时间复杂度(操作次数)来对它们进行比较。  

当一个算法执行时所使用的计算机内存总量就是该算法的空间复杂度。不过本文不会讨论空间复杂性(为了使本文简短一些)。  

时间复杂度

那么，时间复杂度就是算法完成其任务所执行的操作次数(考虑到每次操作花费的时间是相同的)。从时间复杂度的角度来看，以最少的操作次数完成任务的算法就是最有效的算法。不过，空间和时间复杂性也受到操作系统和硬件等因素的影响，但是本文不讨论这些因素。 

我们将举一个例子来理解时间复杂度，通过解决一个特定的问题来比较两种不同的算法。 

这个问题是检索。我们需要在一个数组中检索一个元素(在这个问题中，我们假设数组是按升序排序的)。为了解决这个问题，我们有两种算法:  

● 线性查找

● 折半查找

假设数组包含10个元素，我们需要找到数组中的数字10。 

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

const search_digit = 10;

线性查找算法将把数组中的每个元素与search_digit进行比较。当它在数组中找到search_digit时，将返回true。  

那让我们计算它执行的操作次数。这里，答案是10(因为它会比较数组中的每个元素)。因此，线性查找用了10次操作来找到给定的元素（这些是这个数组的最大操作次数；在线性查找的情况下，这也被称为一个算法最坏的情况）。  

一般来说，线性查找在最坏的情况下需要n次操作(n是数组的大小)。 

 让我们检验一下折半查找算法在这种情况下的表现。 

很容易通过这个例子来理解折半查找：  

如果我们尝试将这个逻辑应用到我们的问题上，那么，我们首先要把search_digit与数组的中间元素进行比较，也就是5。由于5小于10，我们将开始在大于5的数组元素中检索search_digit。以相同的方式继续进行，直到我们得到所需的元素10。 

然后，计算折半查找找到所需元素所需的操作次数。大约需要四次操作。这是折半查找最坏的情况。这表明执行的操作次数与数组的总长度之间存在对数关系。 

操作次数= log(10) = 4(近似值) 

以2为底 

我们可以将这个结果归纳到折半查找中: 

对于一个大小为n的数组来说，它的折半查找执行的操作次数为：log(n)  

大O符号

在上面的语句中，我们看到对于大小为n的数组，线性搜索将执行n个运算以完成搜索。 另一方面，二进制搜索执行log（n）个操作数（均为最坏情况）。 我们可以将其表示为图形（x轴：元素数，y轴：操作数）。

从图中可以很清楚地看出，线性搜索的复杂度增加速度远快于二分法搜索的速度。

当我们分析算法时，我们使用一种表示法来表示其时间复杂度，并且该表示法是大O符号。

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

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

二分法搜索：O(log n)

线性搜索：O(n)

快速排序：O(n * log n)

选择排序：O(n * n)

旅行推销员：O(n！)

总结

如果您仍在阅读本文，我将非常感谢您的努力。 现在，您必须在思考-为什么理解时间复杂度如此重要？

我们知道对于少量元素（例如10），二分法搜索和线性搜索执行的操作数之间的差异并不大。 但是在现实世界中，大多数时候，我们要处理的数据量很大。

例如，如果我们要搜索40亿个元素，那么在最坏的情况下，线性搜索将需要40亿次运算才能完成其任务。 二进制搜索仅需32次操作即可完成此任务。 那是很大的不同。 现在，假设完成一项操作需要1毫秒，那么二进制搜索将仅花费32毫秒，而线性搜索将花费40亿毫秒（约46天）。 那是很大的不同。

这就是为什么在涉及大量数据时研究时间复杂性变得重要的原因。

一THE END一

免责声明：本文来自互联网新闻客户端自媒体，不代表本网的观点和立场。

合作及投稿邮箱：E-mail:editor@tusaishared.com