算法的时间复杂度

[Zakariyya]

度量以一个程序（算法）执行时间的两种方法

1. 事后统计的方法 （这种方式，要在同一台计算机的相同状态下运行，才能比较哪种算法速度更快）
2. 事前估算 （通过分析某个算法的时间复杂度来判断哪个算法更优）

算法时间复杂度

时间频度

• 忽略常数项
• 忽略低次项 n
• 忽略系数

时间复杂度

1. 常数阶 O(1)
2. 对数阶 O(log2 n)
3. 线性阶 O(n)
4. 线性对数阶 O(nlog N)
5. 平方阶 O(n^2)
6. 立方阶 O(n^3)
7. K次方阶 O(n^k)
8. 指数阶 O(2^n)

说明：

• 常见的算法时间复杂度由小到大依次为：O(1) < O(log2 n) < O(nlog2 n) < O(n^3) < O(n^k) < O(2^n)， 随着问题规模 n的不断增大，上述时间复杂度不断增大，算法的执行效率越低
• 应避免使用指数阶的算法

平均时间复杂度和最坏时间复杂度

排序法	平均时间	最差情形	稳定度	额外空间	备注
冒泡	O(n^2)	O(n^2)	稳定	O(1)	n小 时较好
交换	O(n^2)	O(n^2)	不稳定	O(1)	n小 时较好
选择	O(n^2)	O(n^2)	不稳定	O(1)	n小 时较好
插入	O(n^2)	O(n^2)	稳定	O(1)	大部分已排序 时较好
基数	O(logR B)	O(logR B)	稳定	O(n)	B是真数(0-9)， R是基数(个十百)
Shell	O(nlogn)	O(n^s)1 < s < 2	不稳定	O(1)	s是所选分组
快速	O(nlogn)	O(n^2)	不稳定	O(nlogn)	n大 时较好
归并	O(nlogn)	O(n^2)	稳定	O(nlogn)	n大 时较好
堆	O(nlogn)	O(nlogn)	不稳定	O(1)	n大 时较好

空间复杂度

1. 空间复杂度是对一个算法在运行过程中临时占用存储空间大小的度量。有的算法需要占用的临时工作单元数与解决问题的规模n 有关，它随着n的增大而增大，当n较大时，将占用较多的存储单元，例如快速排序和归并算法就属于这种情况
2. 从用户使用体验上，更看重程序执行速度，一些缓存产品（redis，memcache）和算法（基数排序）本质就是用空间交换时间