简单理解算法时间复杂度

前言

这里的解释说明都是从知乎上 《如何理解算法时间复杂度的表示法O(n^2) 、O(n)、O(1)、O(nlogn))》 这个问题里面总结而来的，主要参考了梦回琼花、invalid s、司马懿、夏目沉吟、罗宸几个回答，摘取总结如下。一些概念上的词语解释，我放在了最后，毕竟以后查阅的时候还是主要查几个常用复杂度所代表的意思。

解释几个常见的时间复杂度

O(1)

理论上来说哈希表就是O(1)。因为哈希表是通过哈希函数来映射，把关键字用哈希函数计算一下，就可以算出理论上是唯一的值，通过这个值就可以直接从表中取出对应的值。和现存数据有多少毫无关系。所以每次执行所需要的时间理论上是恒定的。

O(n)

这个是说随着样本数量的增加，复杂度也随之线性增加。比如说简单的数数，从1数到100，需要100秒，那从1数到200，基本上就是大于等于200秒。所以数数就是一个O(n)复杂度的事情。

O(n^2)

这个表示计算的复杂度随着样本个数的增加成平方数的增长。比如冒泡算法，选择算法等等。举个简单例子，在一大堆杂乱的试卷中，要选出最高的分数卷子，然后放在一旁，在然后选出第二高的分数卷子，排在刚才第一高分数的后边，以此类推。每次选出当前最高分数的试卷的时候都需要从头到尾的遍历一边剩下的所有卷子，所以遍历所耗时间是O(n)，然后有n张卷子，所以总共需要O(n^2)的时间。或者换一个说法，每增加1的时候，都给算法执行带来了n量级的消耗时间那这种算法的时间复杂度就是O(n^2)。

O(logn)

这里面恐怕最难理解的就是这个log是怎么来的，最典型的代表就是二分查找算法。还是设想一堆试卷，已经从高到低按照分数排列了，然后我们想要查找是否存在59分的试卷。怎么查找呢？先将排好序的试卷从中间一分为2，把试卷堆由中间分成上下两堆，看中间这份是大于59还是小于59，如果大于，就剩下上面那堆，抛弃下面那堆，如果小于，就反之留下下面那堆，抛弃上面那堆。然后在用同样的方法，每次从剩下的一堆试卷中筛选一半，然后丢掉另一半，直到只剩下最后一张试卷为止。

假如有32份试卷，第一次筛选后还剩下16份，第二次筛选后还剩下8份，第三次筛选后还剩下4份，直到第五次筛选后 还剩下最后一份。用数字表示就是(((((32 \div 2) \div 2) \div 2) \div 2) \div 2) = 1，转换一下就是32 =2^5，又或是以2为底32的对数是5，数学表示就是log_232=5，所以我们需要log_232次，才能带出“找到”或者“没有找到”的结果。

所以时间的复杂度就是log_2n。当然你也可以说你三分查找，每次抛弃三分之二可不可以？当然可以，但是算法复杂度在这里是忽略常数的，所以不管是以2为底，还是以什么数为底，都统一写成logn的形式。

O(nlogn)

知道了O(logn)的解释，那解释这个就简单了，前面的n代表了执行n次logn的操作。理解这一点，就可以理解快速排序的复杂度为什么是O(nlogn)了，比如对一堆带有序号的书进行排序，怎么快呢？就是随便先选一本，然后把号码大于这本书的扔右边，小于这本书的扔左边。因为每本书都要比较一次，所以这么循环一次的复杂度是O(n)，那么快速排序需要我们循环多少次呢？这里又回到了二分查找的逻辑，每次把书堆一分为二，请问分多少次才能只剩下一本书呢？当然是logn次了，所以最后我们需要O(nlongn)次了。

什么是算法的"复杂度"？

算法的复杂度指的是：为了执行给定算法，所需要的计算资源跟问题规模的函数关系。

特别的，讲算法的时间复杂度的时候，关心的计算资源就是时间，或者说时钟周期的个数。讲空间复杂度的时候，关心的计算资源就是空间，或者说暂用的存储空间的字节数