概念

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

  • 固定部分。这部分空间的大小与输入/输出的数据的个数多少、数值无关。主要包括指令空间（即代码空间）、数据空间（常量、简单变量）等所占的空间。这部分属于静态空间。
  • 可变空间。这部分空间的主要包括动态分配的空间，以及递归栈所需的空间等。这部分的空间大小与算法有关。

示例

1
2
3
4
5
def reverse(a,b):
    n = len(a)
    for i in range(n):
        b[i] = a[n-1-i]
        #完成列表的逆序

调用reverse方法时，要分配的内存空间包括：引用a，引用b、局部变量n、局部变量i。因此f(n)= 4,该算法的空间复杂度为S（n）=O（1）
注：通常，我们都是用“时间复杂度”来指运行时间的需求，是用“空间复杂度”指空间需求。当直接要让我们求“复杂度”时，通常指的是时间复杂度。显然对时间复杂度的 追求更是属于算法的潮流！