算法复杂度

程序执行相关资源:

CPU消耗   (指令数量)

内存空间     (数量规模,包括常量、变量)

数据通信     (数据请求次数、网络链接、磁盘访问、网络数据包等)

O 记号法

复杂度 标记符号 描述
常量(Constant)  O(1) 操作的数量为常数,与输入的数据的规模无关。

n = 1,000,000 -> 1-2 operations

对数(Logarithmic)  O(log2 n) 操作的数量与输入数据的规模 n 的比例是 log2 (n)。

n = 1,000,000 -> 30 operations

线性(Linear)  O(n) 操作的数量与输入数据的规模 n 成正比。

n = 10,000 -> 5000 operations

平方(Quadratic)  O(n2) 操作的数量与输入数据的规模 n 的比例为二次平方。

n = 500 -> 250,000 operations

立方(Cubic)  O(n3) 操作的数量与输入数据的规模 n 的比例为三次方。

n = 200 -> 8,000,000 operations

指数(Exponential)  O(2n)

O(kn)

O(n!)

指数级的操作,快速的增长。

n = 20 -> 1048576 operations