算法从入门到精通4之算法复杂度 什么叫算法复杂度

一、概述

衡量算法复杂度的还有另一个指标就是空间复杂度。空间复杂度就是在执行算法过程中需要分配的内存空间的渐进性大小。空间复杂度和时间复杂度是两个共同衡量算法复杂度的指标；都是用大O辅导表示复杂系数，记作O(f(n))。

二、空间复杂度

概述中提到过，空间复杂度就是一个算法在执行过程中所需要的内存空间。接下来通过一些示例给大家说明空间复杂度的计算方式。

示例1：

int sum=0;
for (int i = 1; i <= n; i++) {
    sum+=i;
}

如上代码，还是计算1加到100的题目。它的时间复杂度是O(n)，那么它的空间复杂度是多少呢？

空间复杂度就是算法运行期间占用内存的多少。那么我们看看上面的代码，有两个位置会分配存储空间，一个是sum的定义，一个是i的定义：

并且，这两个int变量的定义，在上述代码中只会定义一遍，不会出现重复定义的现象，所以上述代码不论n是多少，都只占用两个int数据类型所需的空间大小。我们称之为2个单位的内存空间。随着n越来越大，也只会占用2个单位的内存空间。 所以上述代码的空间复杂度是O(1)。O(1)中的1代表的是一个常量，并不是说只占1个单位空间。所占单位空间不论是1个单位、2个单位、亦或是10个单位，只要不受n的变化而变化，这样的固定空间大小的空间复杂度统一记作O(1)。

但是，如果代码写成如下格式，大家想想，其空间复杂度是多少呢？

int sum=0;
for (int i = 1; i <= n; i++) {
        sum+=i;
    int m=sum;
}

如上，在for循环中定义了一个整数变量m，随着n越来越大，每次执行int m=sum这段代码的时候，都会在内存里面分配存储空间。如果n为10，就会分配10+2个单位的存储空间（2是sum和i的存储空间，10是m被定义10次要分配的空间）；如果将10替换成n，那么就是n+2个单位的存储空间；利用极限思想，n->∞，n+2中的2可以忽略不计，所以空间复杂度就是O(n)。

三、递归的空间复杂度

还是1加到100，如果用递归来做的话，代码如下：

static int sum;
public static int algorithm3(int n){
    if (n<1) return sum;
    sum+=n;
    return algorithm3(n-1);
}

上述，是利用递归计算1加到100。那么它的空间复杂度是多少呢？此处有几个问题跟大家说清楚，java中的方法在任何时候只会被初始化一次，也就是说方法中的参数定义只会执行一次。那么再想想上面的空间复杂度是多少呢？

我就不买关子了，上述递归算法的空间复杂度是O(n)。原因是递归的特殊性，每递归一次，内存就会分配一个空间用来存储algorithm3方法上一次执行的状态，随着n的增大，内存要存储algorithm3这个方法的n次执行状态，就要分配n个单位的存储空间，所以空间复杂度记为O(n)。

四、常见的空间复杂度

常见的空间复杂度有三个，分别是O(1)，O(n)，O(log2n)。O(1)和O(n)我们本文都有介绍过了，O(log2n)的空间复杂度在后面我们讲解算法中的快速排序的时候会涉及到。当然，更复杂的空间复杂度肯定是有的，但是我们暂时用不到，也可以不用理会。

五、总结

至此，时间复杂度和空间复杂度这两个用来衡量一个算法好坏的指标就跟大家介绍清楚了，后面我们的学习将会从排序、查找、数据结构、常用算法等方面进一步介绍算法的更多知识。同时也欢迎大家留言点评，共同讨论学习才会有进步。