好程序员Java培训分享之算法入门到精通-算法复杂度(二)，一、概述：上一篇我们讲解的是时间复杂度，更多的内容是让大家理解大O符号、以及时间复杂度是如何计算的。本章节将会带大家认识一下常见的时间复杂度。

　　二、常见时间复杂度

　　2.1、O(1)

　　O(1)是zuihao的算法时间复杂度，也就是说同比效率最高的算法。其中的1表示的不是1次，之前有个同学问我，如果是消耗2个单位时间的时间复杂度是不是记为O(2)呢?不是。不论算法消耗几个单位时间，只要是这个时间不随着n的渐进性变化而变化，也就是这个单位时间永远都是2个、或者永远都是10个。这样的时间复杂度都记作O(1)。

　　是不是所有O(1)时间复杂度的算法的执行时间都相等呢?不是，上面说了O(1)可能是2个单位时间，也可能是10个单位时间;再者，电脑的硬件不同、环境不同，哪怕同一个算法在不同机器上执行所消耗的时间都是不一样的，但是他们的时间复杂度都是O(1)。所以时间复杂度都是O(1)的，所消耗的时间是不相等的。如下图，增长是一条水平的直线。

　　2.2、O(n)

　　O(n)是线性增量的时间复杂度，也成为线性时间复杂度。因为其时间变化是线性增长的。

　　在此，先要说清楚什么是线性增长，线性增长也可以称为等速增长。比如2n+2这个函数就是线性增长，因为当n为1的时候2n+2=4，当n=2的时候为6，当n=3的时候为8，每次都是增量都是2，等量增长，也是等速增长。这样的增长成为线性增长。

　　2.3、O(n^2)

　　O(n^2)这种时间复杂度的算法，随着n的增大其计算速度也是越来越慢，慢下来的速度是非常快。也就是相比O(n)而言，时间复杂度是O(n^2)的算法执行时间相对来说所花费的时间更长。比如冒泡排序就是这种时间复杂度。

　　2.4、O(logn)

　　O(logn)是一种对数类型的时间复杂度。

　　对数的概念先给大家复习一下，比如2^x=n,转换对数就是以2为底数n的对数，记作log2 n(此处的2应该放到log下角，并且写小一点，但是计算机打不出来我用空格以示区分)。比如以2为底8的对数是3，记作log2 8=3.

　　所以，当n非常大的时候，时间复杂度的增长反而比较小。因为n=256的时候，log2 256=8。也就是n为256但是O(logn)时间复杂度反而只是8。因此O(logn)复杂度的算法也是相对来说比较优秀的算法。

　　2.5、O(nlogn)

　　O(nlogn)时间复杂度的概念在了解了O(logn)之后应该会有一个粗略的推测了。比如log2 256=8，那么nlog就是256(log2 256)=256*8，这种增速比O(n)要大，但是比O(n^2)要小。

　　总结

　　时间复杂度上O(1)<o(logn)<o(n)<o(nlogn)<o(n^2)，在实际开发中，我们对算法的优化尽量往o(logn)方向靠拢，就会更节省时间。< p="">

　　本节将一些常见的时间复杂度列出来，目的有两个，一是让大家能更深入一点了解时间复杂度;二是对后面可能出现的一些数学公式做一些复习。以便后面的内容能直接引用。

　　算法的时间复杂度还有很多其他的复杂度表示函数，这个取决于算法的复杂性，上面列举的时间复杂度基本是我们常见的了。本节知识作为了解的内容，后面我们在讲解到具体算法的时候，会结合具体例子讲解对应的时间复杂性。同时也欢迎大家留言点评讨论，一起成长进步。