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

秒速五厘米 2021-10-15 01:25 304阅读 0赞

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

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

![70][]

时间复杂度这个东西，其实更准确点说应该是描述一个算法在问题规模不断增大时对应的时间增长曲线。所以，这些增长数量级并不是一个准确的性能评价，可以理解为一个近似值，时间的增长近似于logN、NlogN的曲线。

![70 1][]

先从O(1)来说，理论上哈希表就是O(1)。因为哈希表是通过哈希函数来映射的，所以拿到一个关键字，用哈希函数转换一下，就可以直接从表中取出对应的值。和现存数据有多少毫无关系，故而每次执行该操作只需要恒定的时间（当然，实际操作中存在冲突和冲突解决的机制，不能保证每次取值的时间是完全一样的）。举个现实的例子，比如我的身后有一排柜子，里面有香蕉（代号B），苹果（代号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，如果大于，就留下上面那堆，别的丢掉，如果小于，就留下下面那堆，丢掉上面。然后按照同样的方法，每次丢一半的试卷，直到丢无可丢为止。

![70 2][]

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

出处：[https://blog.csdn.net/qq\_34229351/article/details/80841482?utm\_source=blogxgwz0][https_blog.csdn.net_qq_34229351_article_details_80841482_utm_source_blogxgwz0]

[JackLiu16]: https://me.csdn.net/JackLiu16
[70]: /images/20211015/1dd51cc459594c63bc40160059f97160.png
[70 1]: /images/20211015/6fa659fc97d84d56a187aba9b017a4f3.png
[70 2]: /images/20211015/918ae55d97ac44cb8f1f172a620afaae.png
[https_blog.csdn.net_qq_34229351_article_details_80841482_utm_source_blogxgwz0]: https://blog.csdn.net/qq_34229351/article/details/80841482?utm_source=blogxgwz0