时间复杂度

作者: 简石榴 | 来源:发表于2019-05-23 13:21 被阅读0次

时间复杂度(下)
day02 四种时间复杂度分析方法
数据结构与算法之美笔记——复杂度分析(下)
算法学习笔记-浅析时间复杂度
sort_algorithm
归并排序图解
时间复杂度和空间复杂度笔记
归并排序 by Python
day09-冒泡排序+优化
时间复杂度和空间复杂度

时间复杂度：在计算机科学中算法的时间复杂度是一个函数，它定性的描述该算法的运行时间，但并不是表示一个程序解决问题需要花多少时间。而是说当问题规模扩大后，程序需要的时间增长得有多快。

也就是说，对于高速处理数据的计算机来说，处理某一个特定数据的效率不能衡量一个程序的好坏，而应该看当这个数据的规模变大到数百倍后，程序运行时间是否还是一样，或者也跟着慢了数百倍，或者变慢了数万倍。不管数据有多大，程序处理花的时间始终是那么多的，我们就说这个程序很好，具有O(1)的时间复杂度，也称常数级复杂度；数据规模变得有多大，花的时间也跟着变得有多长，这个程序的时间复杂度就是O(n)，比如找n个数中的最大值；而像冒泡排序、插入排序等，数据扩大2倍，时间变慢4倍的，属于 $O(n^2)$ 的复杂度。还有一些穷举类的算法，所需时间长度成几何阶数上涨，这就是 $O(a^n)$ 的指数级复杂度，甚至 $O(n!)$ 的阶乘级复杂度。

不会存在 $O(2*n^2)$ 的复杂度，因为前面的那个“2”是系数，根本不会影响到整个程序的时间增长。同样地， $O (n^3+n^2)$ 的复杂度也就是 $O(n^3)$ 的复杂度。因此，我们会说，一个 $O(0.01*n^3)$ 的程序的效率比 $O(100*n^2)$ 的效率低，尽管在n很小的时候，前者优于后者，但后者时间随数据规模增长得慢，最终 $O(n^3)$ 的复杂度将远远超过 $O(n^2)$ 。我们也说， $O(n^{100})$ 的复杂度小于 $O(1.01^n)$ 的复杂度。
前面的几类复杂度被分为两种级别，其中后者的复杂度无论如何都远远大于前者：一种是 $O(1)$ , $O(log(n))$ , $O(n^a)$ 等，我们把它叫做多项式级的复杂度，因为它的规模n出现在底数的位置；另一种是 $O(a^n)$ 和 $O(n!)$ 型复杂度，它是非多项式级的，其复杂度计算机往往不能承受。当我们在解决一个问题时，我们选择的算法通常都需要是多项式级的复杂度，非多项式级的复杂度需要的时间太多，往往会超时，除非是数据规模非常小