计算复杂度（终于把时间复杂度和空间复杂度）

前言

俗话说，“语言只是工具，算法才是程序的灵魂”。对于程序员来说，算法始终是一个绕不开的门槛。近两年，越来越多的互联网公司在招聘环节注重算法的考察。

什么是好的算法？

我们通常有下面两个指标：

空间复杂度：根据算法写成的程序在执行时占用存储单元的长度。时间复杂度：根据算法写成的程序在执行时耗费时间的长度。

在实践中或面试中，我们不仅要能够写出具体的算法来，还要了解算法的时间复杂度和空间复杂度，这样才能够评估出算法的优劣。当时间复杂度和空间复杂度无法同时满足时，还需要从中选取一个平衡点。

如何计算时间复杂度？

常见的时间复杂度量级有：

常数阶O(1)对数阶O(logN)线性阶O(n)线性对数阶O(nlogN)平方阶O(n²)立方阶O(n³)指数阶(2^n、n!、n^n)

上面从上至下依次的时间复杂度越来越大，执行的效率越来越低。优劣排序如下：O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3)< O(2^n) < O(n!) < O(n^n)

求解算法复杂度一般分以下几个步骤：

找出算法中的基本语句：算法中执行次数最多的语句就是基本语句，通常是最内层循环的循环体。计算基本语句的执行次数的数量级：只需计算基本语句执行次数的数量级，即只要保证函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析，使注意力集中在最重要的一点上：增长率。用大Ο表示算法的时间性能：将基本语句执行次数的数量级放入大Ο记号中。

其中用大O表示法通常有三种规则：

用常数1取代运行时间中的所有加法常数；只保留时间函数中的最高阶项；如果最高阶项存在，则省去最高阶项前面的系数；

下面通过具体的实例来说明以上的推算步骤和规则：

（1） 常数阶O(1)

无论代码执行了多少行，只要是没有循环等复杂结构，那这个代码的时间复杂度就都是O(1)，如：

int i = 1; int j = 2; ++i; j++; int k = i + j;

上述代码执行时，单个语句的频度均为1，不会随着问题规模n的变化而变化。因此，算法时间复杂度为常数阶，记作T(n)=O(1)。这里我们需要注意的是，即便上述代码有成千上万行，只要执行算法的时间不会随着问题规模n的增长而增长，那么执行时间只不过是一个比较大的常数而已。此类算法的时间复杂度均为O(1)。

（2）对数阶O(log n)

int i = 1; // ① while (i <= n) { i = i * 2; // ② }

在上述代码中，语句①的频度为1，可以忽略不计。

语句②我们可以看到它是以2的倍数来逼近n，每次都乘以2。如果用公式表示就是1*2*2*2…*2 <=n，也就是说2的x次方小于等于n时会执行循环体，记作2^x <= n，于是得出x<=logn。也就是说上述循环在执行logn次之后，便结束了，因此上述代码的时间复杂度为O(log n)。

其实上面代码的时间复杂度公式如果精确的来讲应该是：T(n) = 1 + O(log n)，但我们上面已经讲到对应的原则，“只保留时间函数中的最高阶项”，因此记作O(log n)。

（3）线性阶O(n)

int j = 0; // ① for (int i = 0; i < n; i++) { // ② j = i; // ③ j++; // ④ }

上述代码中，语句①的频度为1，②的频度为n，③的频度为n-1，④的频度为n-1，因此整个算法可以用公式T(n)=1+n+(n-1)+(n-1)来表示。进而可以推到T(n)=1+n+(n-1)+(n-1)=3n-1，即O(n)=3n-1，去掉低次幂和系数即O(n)=n，因此T(n)=O(n)。

在上述代码中for循环中的代码会执行n遍，因此它消耗的时间是随着n的变化而成线性变化的，因此这类算法都可以用O(n)来表示时间复杂度。

（4）线性对数阶O(nlogN)

for (int m = 1; m < n; m++) { int i = 1; // ① while (i <= n) { i = i * 2; // ② } }

线性对数阶要对照对数阶 O(log n)来进行理解。上述代码中for循环内部的代码便是上面讲到对数阶，只不过在对数阶的外面套了一个n次的循环，当然，它的时间复杂度就是n*O(log n)了，于是记作O(nlog n)。

（5）平方阶O(n²)

int k = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { k++; } }

平方阶可对照线性阶来进行理解，我们知道线性阶是一层for循环，记作O(n)，此时等于又嵌套了一层for循环，那么便是n * O(n)，也就是O(n * n)，即O(n^2)。

（6）立方阶O(n³)

int a = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { for (int k = 0; k < n; k++) { a++; } } }

同理，立方阶O(n³)相对于平方阶O(n²)，只不过是多嵌套了1层循环而已。那么便是n * O(n*n)，也就是O(n * n * n)，即O(n^3)。

（6）指数阶O(2^n)

int Fibonacci(int number) { if (number <= 1) return number; return Fibonacci(number - 2) + Fibonacci(number - 1); }

O(2^n)，表示一个算法的性能会随着输入数据的每次增加而增大两倍，典型的方法就是上述代码中裴波那契数列的递归计算的实现。

严格来说，斐波那契数列的时间复杂度的紧界不是 O(2^n)，而是O(((1+√5）/ 2)^n)，有兴趣的同学可以自己推导一下～

如何计算空间复杂度？

程序执行除了需要存储空间、指令、常数、变量和输入数据外，还包括对数据进行操作的工作单元和存储计算所需信息的辅助空间。存储空间通常包括：指令空间（即代码空间）、数据空间（常量、简单变量）等所占的固定部分和动态分配、递归栈所需的可变空间。其中可变空间与算法有关。

一个算法所需的存储空间用f(n)表示。S(n)=O(f(n))其中n为问题的规模，S(n)表示空间复杂度。

下面看两个常见的空间复杂度示例：空间复杂度O(1)和O(n)：

（1）空间复杂度 O(1)

int i = 1; int j = 2; int k = i + j;

上述代码中临时空间并不会随着n的变化而变化，因此空间复杂度为O(1)。

总结一下就是：如果算法执行所需要的临时空间不随着某个变量n的大小而变化，此算法空间复杂度为一个常量，可表示为 O(1)，即 S(n) = O(1)。

（2）空间复杂度 O(n)

int j = 0; int[] m = new int[n]; for (int i = 1; i <= n; ++i) { j = i; j++; }

上述代码中，只有创建int数组分配空间时与n的大小有关，而for循环内没有再分配新的空间，因此，对应的空间复杂度为S(n) = O(n)。