如何理解表示算法的时间复杂度。O(n²)、O(n)、O(1)、O(nlogn)等？

2018年10月30日 00:09:14 JackLiu16 阅读数 127

这件事的时间复杂性，其实更准确地说，应该是描述一个算法在问题规模上增加了相应的时间增长曲线。因此，这些增长顺序并不是一个准确的业绩评估，可以理解为一个近似值，增长的时间是相似的。logN、NlogN的曲线。

先从O(1)理论上，哈希表是。O(1)。因为哈希表是由哈希函数映射的，所以您将获得一个关键字并使用哈希函数对其进行转换，以直接从表中获取相应的值。它与现有数据量无关，所以执行每个操作只需要不变的时间(当然，实际操作中存在冲突和冲突解决机制，不能保证每个值的时间完全相同)。举一个现实的例子，比如，我身后有一排放着香蕉(代号)的橱柜B)、Apple(代码A)、葡萄(G)，现在你说A，我赶紧把苹果递给你；你说B，我很快地把香蕉递了过来。即使你加入菠萝(P)、火龙果(H)，但是你说了一个代号，我递给你相应的水果，这个速度几乎没有变化。

至于O(n)这意味着随着样本数的增加，复杂性也会线性增加。典型的，比如数数。如果一个人来自1数到100，需要100秒，然后从。1到200，基本上不会减少200秒，所以计数是一种  事物的复杂性。一般来说，需要顺序处理的算法的复杂性并不低O(n)。例如，如果我们想要设计一个算法，从一堆乱七八糟的试卷中找到最高分，我们需要从头到尾阅读每一张试卷。显然，试卷越多，花费的时间就越多。这是一个O(n)复杂性算法。

而O(n²)也就是说，计算的复杂性随着样本数的平方而增加。这个例子是在算法中，也就是比较沮丧的那类分组，比如冒泡、选择等。按照我们刚才提到的试卷的例子，我们找出最高分后，把它放在一边，开始另一堆，然后用同样的方法找到第二高分，放在新的一堆上...... 我们确实是这样做的n第二，试卷按照分数从低到高排列。因为有很多n一张试卷，所以我们必须做这样的动作，把试卷翻过来，找出最高分。n时间，每个时间的复杂性是O(n),那么n个O(n)自然就是O(n²)。

例如，在构建网络时，每个点都与其他点相连。显然，每当我们添加一个点时，我们实际上需要在该点和所有现有点之间建立一个连接，而现有点的数量是n，所以每次增加1，有必要增加n连接，那么如果我们增加n那么这一点呢，那么连接的数量自然是n²量级了。

无论是翻卷还是组网，每多一张试卷、每一个加分都需要带到算法执行者手中。n工作量大时，该算法的复杂性为(n²) 。

然后是O(nlogn)  在常见算法的复杂性中，这可能是相对难以理解的。就是这个log你是怎么到这里来的。前面的那个n，表示执行n次log(n)行动，所以请理解。log(n)，明白吗nlog(n)。

O(logn)算法复杂性，通常如二进制查找。想象一下，一堆试卷，按照分数从上到下排列。我们现在想要找出是否有59试卷。我该怎么办？首先转到中间，把试卷堆从中间分成上堆和下堆，看看中间的是大还是小59，如果大于，离开顶部堆，其他扔掉，如果小于，离开底部堆，扔掉顶部。然后按照同样的方法，一次丢掉一半的试卷，直到你不能丢为止。

详见https://www.zhihu.com/question/21387264

出处： https://blog.csdn.net/qq_34229351/article/details/80841482?utm_source=blogxgwz0