12 算法分析之空间复杂度

在前一篇中，我们探讨了算法的时间复杂度，通过测量算法运行所需时间的增长来评估算法的效率。这一篇将重点讨论另一个重要概念：空间复杂度。空间复杂度是算法在运行时所需内存空间的量度。

什么是空间复杂度？

空间复杂度是指算法执行时所需空间的度量，通常用大写字母S表示。它包含了几个部分：

1. 固定部分：这部分是算法在执行过程中所需的基本存储空间的量，通常包括常量、变量、输入数据等。它的大小不随输入数据的大小而变化。
2. 可变部分：这部分是随着输入数据的改变而发生变化的存储空间。比如，递归调用所需的栈空间和动态分配的存储空间等。

总体来说，空间复杂度的表达式通常是形如 $S(n)$，其中 $n$ 是输入数据的规模。

示例 1：简单变量的空间复杂度

考虑以下简单的函数，它计算两个数字的和：

def add(a, b):
    return a + b

在这个例子中，所需的空间复杂度是常量级别 $O(1)$，因为无论输入的大小如何，它只使用了有限的变量（a、b 和 返回值）。

示例 2：数组的空间复杂度

现在，让我们考虑一个函数，它接受一个列表并计算列表中所有数字的和：

def sum_list(nums):
    total = 0
    for num in nums:
        total += num
    return total

在这个例子中，nums 是一个大小为 $n$ 的输入列表。虽然 total 是一个常量空间 $O(1)$，但 nums 列表的大小是 $n$。因此，总的空间复杂度是 $O(n)$，因为我们需要存储这个大小为 $n$ 的列表。

示例 3：递归的空间复杂度

递归算法通常会占用更多的空间，因其每次调用都需要在调用栈上分配空间。以计算斐波那契数列的递归实现为例：

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

在这个实现中，每当我们调用 fibonacci 函数时，都需要在栈上开辟空间用来存储每次调用的中间状态。对于输入 n，最大栈深度为 n，因此其空间复杂度为 $O(n)$。

此外，如果我们使用动态规划优化这个计算过程，空间复杂度可以减少到 $O(1)$:

def fibonacci_dynamic(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

在这种情况下，我们只使用了两个变量 a 和 b，所以空间复杂度是 $O(1)$，更为高效。

总结

空间复杂度是分析算法时的一个重要维度，它帮助我们了解算法在运行时所需的内存资源。通过理解和计算空间复杂度，我们可以更有效地选择合适的算法以适应给定的资源限制。在不同的实现中，空间复杂度可能有显著差别，这也是优化算法时需要关注的一个方面。

在下一篇中，我们将深入探讨大O表示法，作为描述空间复杂度和时间复杂度的主要工具。通过这一章的学习，你将能够在评估算法时更全面地考虑其性能。