另一个算法评测标准---空间复杂度

　　前言

　　在上一篇文章中，耀哥给大家介绍了时间复杂度的概念，这一次耀哥将会给大家介绍评价算法优劣的另一个评测标准---空间复杂度。

　　一. 空间复杂度的概念

　　空间复杂度(Space Complexity)，是对一个算法在运行过程中临时占用存储空间大小的量度。值得注意的是，时间复杂度不是用来计算程序具体耗时的，空间复杂度也不是用来计算程序所占的具体内存大小，它们都只是一个量度而已。

　　二. 常见的空间复杂度

　常数阶O(1)

　　int sum = 0;

　　for(int i=0;i<n;i++){< p="">

　　sum=sum+i;

　　}

 　　此例中，不管n变得多大，都只有2个变量占用内存，内存的占用是一个常数，记住O(1)即可。

　　O(n)

　　int sum = 0;

　　for(int i=0;i<n;i++){< p="">

　　sum=sum+i;

　　int m = sum;

　　}

 　　我们注意看此案例中，在for循坏中，变量m一共被声明了n次，再加上sum与i的声明，一共分配的内存有n+2次。其中，2可以忽略，所以算法的空间复杂度为O(n)

　O(Log2N)

 　　另一个常见的空间复杂度是O(Log2N)，我们来看看下面这段代码，它的空间复杂度就是O(Log2N)，大家自己考虑一下是不是这样?　

　int sum = 0;

　　for(int i=0;i<n;i++){< p="">

　　sum=sum+i;

　　int m = sum;

　　i= 2*i;

　　}

 　　三. 结语

　　经过以上几个案例，耀哥大致给同学们介绍了一下常见的几种空间复杂度。值得注意的是，随着计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。所以我们如今已经不再需要特别关注一个算法的空间复杂度，大多数时候都是用空间换取时间。但如果是某些存储容量比较小的微控制器，例如单片机等，还是需要考虑一下空间复杂度的。