1、线性查找法的复杂度

很容易看出，这个算法的复杂度为 O(n)。

2、一个数组中的元素可以两两组成哪些数据对？ O(n²)

需要实现一个算法，这个算法用于：找到一个数组中的元素可以两两组成哪些数据对？
①、在不要求顺序的情况下，即data[i],data[j]和data[j],data[i]看作同一个数据对；
②、每一个元素自己和自己不能组成数据对，即data[i],data[i]不是数据对。

这个算法的代码如下：

注意，j从i+1开始。
可以分析得出，这个算法的复杂度为O(n²)。

虽然是2重循环，但是循环执行的次数并不是nn，其实执行的次数为1/2n²，但是1/2作为常数，不重要。

3、遍历一个n*n的二维数组 O(n²)

我们来实现一个需求：遍历一个n*n的二维数组 ，代码如下：

上述代码的时间复杂度是O(n²)。
注：

在做复杂度分析时，一定要明确n是谁？

假设遍历一个aa的二维数组 O(a²)=O(n)；
而 aa=n，上面的n表示的是维度为n（每一个维度的元素个数都是n），下面的n表示的是元素总数为n。

看时间复杂度也好，总结时间复杂度也好，一定一定要明确n到底谁？

4、数字n的二进制位数 O(logn)

我们来实现一个需求：求解数字n的二进制位的位数？
如何理解位数，我们来举个例子，一看就懂：
16这个数字的10进制位数有几位？
有2位嘛，1和16

520这个数字的10进制位数有几位？
3位嘛，5、2、0

我们看下这个算法的实现的伪码：

上面伪码的时间复杂度是：O(logn)。

不同的底数相差的只是一个常数而已，可以复习下高中数学的换底公式；

所以，最终我们对数复杂度都是不关注底数的，都是O(logn)。

注意，分析算法复杂度的时候，也不能只看循环个数。

这里n每次除以2，而不是每次减1，所以它到0的速度非常快……所以不是O(n)级别，而是O(logn)级别。

5、求解数字N的所有约数？ O(n)、O(√n) ：根号n

我们来实现一个需求：我们来实现一个需求。
首先需要回顾下约数的概念，假设a是n的约数，表示n除以a没有余数，即n可以整除a。

接着，我们来对上述算法做一个优化：

再次强调，看算法复杂度，不能看循环个数。
上述两个算法都是一重循环，但他们循环的结束条件不同，优化前的算法是i<=n，优化后的是i*i<n，所以实际上这两个算法的执行次数是非常不同的。
一个是n，一个是根号n。

所以这个算法的实现，有2种复杂度：
O(n)和O(√n) ：根号n。。

6、求所有长度位n的二进制数字的个数？ O(2^n)；2的n次方

我们来实现一个需求：求所有长度位n的二进制数字的个数？

如何理解这个题目，比如，所有长度位3的二进制数字，一共有几个？

一共有8个，分别是从0到7
0、1、10、11、100、101、110、111

比如，所有长度位4的二进制数字。
一共有16个，分别是从0到15
0、1、10、11、100、101、110、111
1000、1001、1010、1011、1100、1101、1110、1111

这里我们就是用排列组合来得到，长度为n，相当于有n个位置，每个位置或者填0，或者填1；
每个位置有2种选择，现在有n个位置，则相当于n个2连续乘起来
222……222=2^n，是2的n次方。

所以，这个算法的复杂度为： O(2^n)，是2的n次方。

7、长度为n的数组的所有排列 O(n!)

我们来是实现一个需求，求解长度为n的数组的所有排列个数。

举个例子，比如，1、2、3的排列个数为6，
1、2、3、4的排列个数为24。
这里用到了数学中的全排列公式。

全排列个数，n！；
所以这个算法的复杂度为：O(n!)。

O(2^n)，n次方复杂度和 O(n!)阶乘复杂度，都是非常高，性能非常差的复杂度。。

O(2^n)，当n为10，基本就是1000了，程序员都熟悉，实际是1024，
当n为20，基本就是1000*1000=100w了，普通程序员都期望追求的年薪数字是吧哈哈
当n为20，基本就是10亿了，你的10个小目标？这么小的目标，MosesMin可不敢有，哈哈哈
甚至当n为100时，科学家统计，它的大小就接近于宇宙中所有原子的个数那么多个了……
所以指数级别是一个非常恐怖的增长。

通常，算法设计上，如果n<=20，可以考虑指数级别的复杂度；如果n>20，指数级别的复杂度是承受不起的。
所以算法设计上，要尽可能避免指数级别的复杂度；
而阶乘的复杂度就更高了，更是需要全力避免。
阶乘级别也一样，n<20可以考虑，大于20就不能考虑了。

8、判断n是否是偶数？ O(1)

判断n是否是偶数？伪码如下：

只有一行代码，所以复杂度为：O(1)。

9、常见算法复杂度总结

结论很重要，要记住：
O(1)<O(logn)<O(√n)<O(n)<O(nlogn)<O(n²)<O(2^n)<O(n!)

注意；
O(nlogn)很重要。

O(logn)<O(√n)如何比较，不做数学推导了，举个例子记一下：
log以2为底的1000是多少，大概是10，因为2的10次方是1024嘛，所以log以2为底的1000大概是10；
1000的根号值是30多，因为30*30=900嘛，所以大概是30。
10<30,所以我们这样记得：O(logn)<O(√n)

logn比n快很多。
n取100w，logn大概是20次左右，而n要100w次；
数据规模100w的时候，n和logn的性能差距在5w倍。

logn和nlogn这样的算法，会非常多，需要学习。
空间复杂度和时间复杂度的计算基本差不多。

时间更值钱，空间不太值钱；
所以算法设计更重视时间复杂度，所以很多算法设计思想的本质更多是以空间换时间。
即：可不可以考虑使用缓存等等.

我们常见算法的复杂度梳理就到这里。

__EOF__