复杂度O

1. big O的含义

在学术界，严格地讲，O(f(n))表示算法执行的上界。比如，归并排序算法的时间复杂度是O(nlogn)的，同时也是O(n^2)

在业界，我们就是用O来表示算法执行的最低上界。所以，我们一般不会说归并排序是O(n^2)的。

2. 例题：

有一个字符串数组，将数组中的每一个字符串按照字母序排序；之后再将整个字符串数组按照字典序排序。整个操作的时间复杂度？

错误答案：O(n*nlogn + nlogn) = O(n^2logn)

正确解答：

假设最长的字符串长度为s；数组中有n个字符串 对着每个字符串排序：O(slogs) 将数组中的每一个字符串按照字母序排序：O(n*slog(s)) 将整个字符串数组按照字典序排序：O(s*nlog(n)) 所以：O(n*slog(s)) + O(s*nlog(n)) = O(n*s*logs + s*n*logn) = O(n*s*(logs+logn)) 整数比较是O(1)，字符串的字典序比较是O(s)， 所以整个字符串数组进行字典序排序是O(s*nlog(n))。

3. 如果要想在1s之内解决问题：

（1）O(n^2)的算法可以处理大约10^4级别的数据；

（2）O(n)的算法可以处理大约10^8级别的数据；

（3）O(nlogn)的算法可以处理大约10^7级别的数据；

递归调用有空间代价，一般递归深度有多少，占用的空间就有多少。

4. 下面程序是O(n^2)的吗?

30n次基本操作：O(n)

5. O(logn)

二分查找法的时间复杂度是O(logn)的

不要看到for循环，就认为是一层O(n)，下面是两个例子

例1：

不是O(n^2)，而应该是O(nlog(n))。

例2:

是O(sqrt(n))。

再来看一下O(logn)的效率：

log2*N / logN = (log2 + logN) / logN = 1 + log2/logN

如果数据规模增加两倍，当数据量很大的时候，后面的一项可以忽略不计，也就是说运行时间几乎没有增长。

从而可以得知：

1.如果可以将顺序查找的问题转成二分查找的问题，那么就能大大提升效率。

2.O(n)和O(logn)有本质差别，同理，O(n^2)和O(nlogn)也有本质差别。

6. 递归

6.1 递归中进行一次递归调用的复杂度分析：

时间复杂度：O(logn)

如果递归函数中，只进行一次递归调用，递归深度为depth；在每个递归函数中，时间复杂度为T；则总体的时间复杂度为O(T*depth)。

例题：

根据前面O(logn)的性质，可知上面的幂运算比O(n)快很多。

6.2 递归中进行多次调用，以两次调用为例：

上面函数和归并排序不同，归并排序每次递归数据量都有减少，也就是分治算法。