时间复杂度分析

算法意义在于在时间和空间中找出最优解

O(f(n)) 表示算法执行的上界
O 表示算法执行的最低上界

O(nlogn + n) = O(nlogn)
O(nlogn + n^2) = O(n^2)
表示规模n一样

O(AlogA+B)
O(AlogA+B^2)

因为A和B并无关系 所以影响规模变量要单独表示出来

排序算法 默认O(nlogn)

经典字符串排序

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

解答：
假设最长字符串长度为s；数组中有n个字符串
对每个字符串排序：O(slogs)
将数组中每一个字符串按照字母序排序：O(n*slog(s))
将整个字符串数组按照字典序排序：O(s* nlog(n))
两次时间相加：
O(n*slog(s)) + O(s* nlog(n)) = O(n*slog(s) + s* nlog(n))
                             =O(sn(logs + logn))

算法复杂度，参考平均情况

数据规模
1s内解决问题
O(n^2) 10^4
O(n) 10^8
O(nlogn) 10^7

空间复杂度
开出多大辅助空间

辅助一个数组 O(n)
二维数组（n^2）
常数空间O(1)

递归调用是有空间代价
递归的深度deep

递归函数时间复杂度
O(T*depth)

均摊复杂度分析

动态数组

防止复杂度震荡