calculate-complexity-of-algorithm.md

如何计算时间复杂度和空间复杂度？

算法

算法对我们来说都很熟悉，简单来说，算法可以理解为解决方案清晰而准确的描述，解决一系列问题的清晰指令。

算法的效率

既然算法是解决问题的描述，那么针对一个问题，可能会有很多种不同的解法，只是不同的算法使用的时间或者消耗的内存不一样，所以我们需要一些标准去衡量算法的优劣。

算法的效率主要由以下两个参数来评估：

• 时间复杂度：评估执行程序所需的时间。估算出程序对处理器的使用程度。
• 空间复杂度：评估执行程序所需的存储空间。估算出程序对内存空间的使用程度。

时间复杂度

一个算法程序执行的时间理论上是无法计算出来的，但是我们有没有必要去执行每个算法进行测试，只需要大概知道哪个算法所花的时间多，哪个算法所花的时间少即可。

一个算法所需要的时间与算法中代码语句的数量成正比，算法中语句的数量越多，算法所花费的时间就越多。

我们把一个算法中的语句执行次数称为时间频度，通常用T(n)表示。

在时间频度T(n)中，当n不断变化，T(n)也会随之不断变化。为了描述这个变化的规律，引入了时间复杂度这一概念。

如果有某一个辅助函数f(n)，在n趋于无穷大时，T(n)/f(n)的极限值是不为零的某一个常数，那么f(n)是T(n)的同数量级函数，记做T(n)=O(f(n))，称为算法的渐进时间复杂度，简称为时间复杂度。

大O表示法

用O(n)来体现算法时间复杂度的记法被称作大O表示法

一般我们直接评估一个算法最坏的时间复杂度。

大O表示法O(f(n))中的f(n)的值可以为1、n、logn、n^2等，所以我们将O(1)、O(n)、O(logn)、O(n^2)分别称为常数阶、线性阶、对数阶和平方阶。

推导大O阶

推导规则：

• 用常数1替代所有加法常数
• 只保留最高阶项
• 去除最高阶的常数

常数阶

a = 1
b = 2

print a / b

这段代码会执行三条语句，算法时间复杂度为O(1)，是常数阶。

算法的执行时间不会随着n的增加而增长，即使算法有上千条语句，执行时间也只是一个比较大的常数。此类算法时间复杂度为O(1)

线性阶

a = 1

while a < n:
  a += 1

这段代码执行语句数和n的大小有关，时间复杂度为O(n)。

算法执行时间随着n的增加成线性增长。

对数阶

a = 1

while a < n:
  a *= 2

在上面的算法中，a每次都会放大两倍，假设循环执行m次，由2^m = n得出m = logn，所以时间复杂度为O(logn)。

平方阶

def test(n):
    for i in range(n):
        for j in range(n):
            print i * j

上面的循环中，代码执行2*n^2+n行，时间复杂度为O(n^2)。

时间复杂度性能比较：

O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(n³)<O(2ⁿ)<O(n!)

空间复杂度

一个程序的空间复杂度指的是运行一个程序所需要的内存大小，一般用S(n)表示空间复杂度。程序执行所需要的空间包括以下两个部分：

• 静态空间：这部分空间大小与输入/输出的数据的个数多少、数值无关。主要包括指令空间(即代码空间)、数据空间(常量、简单变量等)所占的空间。
• 可变空间：主要是动态分配的空间及递归所需的空间。