算法复杂度

算法复杂度分为时间复杂度和空间复杂度。

时间复杂度——指执行算法所需要的计算工作量；

空间复杂度——指执行这个算法所需要的内存空间。

1 时间复杂度

1.1 概念

时间复杂度（时间复杂性），定性的描述算法的运行时间，这是一个代表算法输入值的字符串的长度的函数。

时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。

1.2 理解

参考：一套图 搞懂“时间复杂度” (opens new window)

例：给你一条长 n 寸的面包，每 10 天吃掉 1 寸，那么吃掉整个面包需要几天？

答：10n，T(n)=10n

例：给你一条长 n 寸的面包，吃掉第 1 寸需要 1 天时间，吃掉第 2 寸需要 2 天时间，吃掉第 3 寸需要 3 天时间……那么吃掉整个面包需要几天？

答：1+2+3+......+ n-1 + n = (1+n)*n/2 = 0.5n² + 0.5n，T(n)= 0.5n² + 0.5n

算法 A 的相对时间是 T(n) = 10n

算法 B 的相对时间是 T(n)= 0.5n² + 0.5n

这两个到底谁的运行时间更长一些？这就要看 n 的取值了。

所以，这时候有了渐进时间复杂度（asymptotic time complexity）的概念，官方的定义如下：

若存在函数 f(n)，使得当n趋近于无穷大时，T(n)/ f(n) 的极限值为不等于零的常数，则称 f(n) 是 T(n) 的同数量级函数。

记作 T(n)= O( f(n) )，称 O( f(n) ) 为算法的渐进时间复杂度，简称时间复杂度。渐进时间复杂度用大写 O 来表示，所以也被称为大 O 表示法。

直白地讲，时间复杂度就是把时间规模函数 T(n) 简化为一个数量级，这个数量级可以是 n、n²、n³……

评价一个算法流程的好坏，先看时间复杂度的指标，然后再分析不同数据样本下的实际运行时间，也就是“常数项时间”

1.3 举例

时间规模函数	时间复杂度
T(n)= 2	T(n)= O(1)
T(n)= 3n	T(n)= O(n)
T(n)= 0.5n2 + 0.5n	T(n)= O(n2)
T(n) = 5logn	T(n) = O(logn)

时间复杂度排序：O(1)< O(logn)< O(n)< O(n^2)

其它形式的时间复杂度：O(nlogn)、O(n³)、O(m*n)、O(2ⁿ)、O(n!)

空间复杂度

额外空间复杂度