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
:表示渐近上限,即最差时间复杂度;
Θ
:表示渐近紧边界,即平均时间复杂度;
Ω
:表示渐近下界,即最好时间复杂度;