概念-空间复杂度
webkong 6/26/2017 概念空间复杂度
想要深入往往是要从概念开始的。
# 定义
一个算法的空间复杂度(Space Complexity)S(n)定义为该算法所耗费的存储空间，它也是问题规模 n 的函数。渐近空间复杂度也常常简称为空间复杂度。
空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。
# 描述
一个算法在计算机存储器上所占用的存储空间，包括（存储算法本身所占用的存储空间）+（算法的输入输出数据所占用的存储空间）+（算法在运行过程中临时占用的存储空间）这三个方面。
算法的输入输出数据所占用的存储空间是由要解决的问题决定的，是通过参数表由调用函数传递而来的，它不随本算法的不同而改变。
存储算法本身所占用的存储空间与算法书写的长短成正比，要压缩这方面的存储空间，就必须编写出较短的算法。
算法在运行过程中临时占用的存储空间随算法的不同而异，有的算法只需要占用少量的临时工作单元，而且不随问题规模的大小 n 而改变，我们称这种算法是“就地（原地）"进行的，是节省存储的算法。这种通常空间复杂度就是 O(1)，有的算法需要占用的临时工作单元数与解决问题的规模 n 有关，它随着 n 的增大而增大，当 n 较大时，将占用较多的存储单元，就是通常所说的 O(n)。
算法原地工作是指算法所需辅助空间是常量，即 O(1)。
# 例
列举一下排序算法的时间复杂度和空间复杂度
| 排序法 | 最差时间分析 | 平均时间复杂度 | 稳定度 | 空间复杂度 |
|---|---|---|---|---|
| 冒泡排序 | O(n2) | O(n2) | 稳定 | O(1) |
| 快速排序 | O(n2) | O(n*log2n) | 不稳定 | O(log2n)~O(n) |
| 选择排序 | O(n2) | O(n2) | 稳定 | O(1) |
| 二叉树排序 | O(n2) | O(n*log2n) | 不稳定 | O(n) |
| 插入排序 | O(n2) | O(n2) | 稳定 | O(1) |
| 堆排序 | O(n*log2n) | O(n*log2n) | 不稳定 | O(1) |
| 希尔排序 | O(n*log2n) | O(n*log2n) | 不稳定 | O(1) |
# 参考
https://zh.wikipedia.org/wiki/%E7%AE%97%E6%B3%95#.E5.A4.8D.E6.9D.82.E5.BA.A6 (opens new window)