时间复杂度

什么是大O ？

n表示数据规模
O(f(n)) 表示运行算法所需要执行的指令数，和f(n)成正比。
寻找数组中的最大/最小值O(n),所需执行的指令数a*n,a是常数

算法A，表示对整个数据扫描一遍，每个数据要执行10000条指令。从图里面看出来，随着数据规模的增长，算法A要优于算法B。

冷知识

1. 在学术界，严格的讲，O(f(n))表示算法执行的上界。什么是上界？比如归并排序的时间复杂度是O(nlogn)，同时也是O(n^2)。在业界，我们就用O来表示算法执行的最低上界，我们一般不会说归并排序的算法时间复杂度是O(n^2)的；
2. O(nlogn + n) = O(nlogn)，当数据量大到一定程度，O(nlogn)占主导。

空间复杂度

多开一个长度为n的辅助数组，空间复杂度就是O(n)
多开一个辅助的二维数组，空间复杂度就是O(n^2)
多开常数空间，O(1)

递归的调用，是有空间代价的。如果递归的深度是n，空间复杂度就是O(n)

常见的复杂度分析