2、时间与空间复杂度
我们一般会关注程序的两个问题：
时间复杂度：这段程序需要花费多少时间才可以执行完成？空间复杂度：执行这段代码需要消耗多大的内存？
有时候时间复杂度和空间复杂度二者不能兼得，我们只能从中取一个平衡点。
下面我们通过Big O表示法来描述算法的复杂度。
2.1、时间复杂度
2.1.1、Big-O
Big-O表示法给出了算法计算复杂性的上限。
T(n) = O(f(n))，该公式又称为算法的渐进时间复杂度，其中f(n)函数表示每行代码执行次数之和，O表示执行时间与之形成正比例关系。
常见的时间复杂度量级，从上到下时间复杂度越来越大，执行效率越来越低：
- 常数阶 Constant Time: O(1)
- 对数阶 Logarithmic Time: O(log(n))
- 线性阶 Linear Time: O(n)
- 线性对数阶 Linearithmic Time: O(nlog(n))
- 平方阶 Quadratic Time: O(n^2)
- 立方阶 Cubic Time: O(n^3)
- n次方阶 Exponential Time: O(b^n), b > 1
- 指数阶 Factorial Time: O(n!)
下面是我从 Big O Cheat Sheet[^1]引用过来的一张表示各种度量级的时间复杂度图表：
2.1.2、如何得出Big-O
所谓Big-O表示法，就是要得出对程序影响最大的那个因素，用于衡量复杂度，举例说明：
O(n + c) =>
O(n)，常量可以忽略；O(cn) =>
O(n), c > 0，常量可以忽略；2log(n)3 + 3n2 + 4n3 + 5 =>
O(n3)，取对程序影响最大的因素。
练习：请看看下面代码的时间复杂度：
答案依次为：O(1), O(n), O(log(n)), O(nlog(n)), O(n^2)
第三个如何得出对数？假设循环x次之后退出循环，也就是说 2^x = n，那么 x = log2(n)，得出O(log(n))
2.2、空间复杂度
空间复杂度是对一个算法在运行过程中占用存储空间的大小的衡量。
- O(1)：存储空间不随变量n的大小而变化；
- O(n)：如：new int[n]；
2.3、常用数据结构复杂度
一些常用的数据结构的复杂度(注：以下表格图片来源于 Big O Cheat Sheet[^1])：
2.4、常用排序算法复杂度
(注：以下表格图片来源于 Big O Cheat Sheet[^1])
关于复杂度符号
O：表示渐近上限，即最差时间复杂度；
Θ：表示渐近紧边界，即平均时间复杂度；
Ω：表示渐近下界，即最好时间复杂度；