# 复杂度O
# 一、big O的含义
在学术界，严格地讲，O(f(n))表示算法执行的上界。比如，归并排序算法的时间复杂度是O(nlogn)的，同时也是O(n^2)
在业界，我们就是用O来表示算法执行的最低上界。所以，我们一般不会说归并排序是O(n^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))。
# 三、如果要想在1s之内解决问题：
- O(n^2)的算法可以处理大约10^4级别的数据；
- O(n)的算法可以处理大约10^8级别的数据；
- O(nlogn)的算法可以处理大约10^7级别的数据；
递归调用有空间代价，一般递归深度有多少，占用的空间就有多少。
# 四、下面程序是O(n^2)的吗?
30n次基本操作：O(n)
# 五、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)也有本质差别。
# 六、递归
# 1. 递归中进行一次递归调用的复杂度分析：
时间复杂度：O(logn)
如果递归函数中，只进行一次递归调用，递归深度为depth；在每个递归函数中，时间复杂度为T；则总体的时间复杂度为O(T*depth)。
例题：
根据前面O(logn)的性质，可知上面的幂运算比O(n)快很多。
# 2. 递归中进行多次调用，以两次调用为例：
上面函数和归并排序不同，归并排序每次递归数据量都有减少，也就是分治算法。