空间复杂度

1. 概述

评估执行程序所需的存储空间。可以估算出程序对计算机内存的使用程度。 一个程序的空间复杂度是指运行完一个程序所需内存的大小。利用程序的空间复杂度，可以对程序的运行所需要的内存多少有个预先估计。一个程序执行时除了需要存储空间和存储本身所使用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为现实计算所需信息的辅助空间。

2. 详细

算法得存储量包括：

1. 程序本身所占空间
2. 输入数据所占空间
3. 辅助变量所占空间

输入数据所占空间只取决于问题本身，和算法无关，则只需分析除输入和程序之外得辅助变量所占额外空间。 空间复杂度是对一个算法在运行过程中临时占用得存储空间大小的量度，一般也作为问题规模n得函数，以数量级形式给出，记作：

$$S(n) = O(g(n))$$