空间复杂度

空间复杂度（Space Complexity）

包括

• 输入数据所占的空间；
• 算法所使用的额外空间；
• 递归栈的空间（对于递归算法）

认识

空间复杂度是衡量一个算法在运行过程中所需的内存空间大小的指标，它描述了随着输入数据规模的增加，算法所需内存空间是如何变化的。与时间复杂度不同，空间复杂度关注的是算法运行时占用的存储空间，而不是执行时间。

空间复杂度通常是以输入规模 n_n_ 为自变量，表示所需内存的变化情况。

算法的空间复杂度通常包括两个方面：

1. 固定空间：与输入数据的规模无关的空间，通常是算法中使用的常数空间（例如，固定数量的变量）。
2. 可变空间：与输入数据规模有关的空间，通常是动态分配的空间（例如，数组、链表、递归栈等）。

空间复杂度的计算

空间复杂度的计算通常关注以下几个方面：

1. 输入数据所占空间：如果算法需要接受输入数据，输入数据本身就占用了内存空间，这部分空间大小通常为 O(n)，其中 n 是输入数据的大小。
2. 算法内部使用的额外空间：包括算法运行过程中使用的变量、数组、链表等数据结构所占的内存空间。
3. 递归调用栈：如果算法是递归的，则每一次递归调用会占用一定的栈空间，这部分空间在分析递归算法时非常重要

常见的空间复杂度

1. O(1) — 常数空间复杂度
   • 算法在执行过程中需要的内存空间是固定的，不随着输入数据规模的增加而变化。
   • 例如，简单的变量存储、常数个数的操作等。
2. O(n) — 线性空间复杂度
   • 算法所需的内存空间与输入数据的规模成正比。
   • 例如，遍历一个数组并将其复制到另一个数组。
3. O(n^2) — 平方空间复杂度
   • 算法所需的内存空间与输入数据规模的平方成正比。
   • 例如，二维数组的存储，或者在一些特定的算法中会产生这样的空间复杂度。
4. O(log n) — 对数空间复杂度
   • 算法的空间复杂度增长速度较慢，通常与递归算法的深度相关。
   • 例如，在某些递归算法（如二分查找）的实现中，栈空间的使用可能是对数级别的。

例子分析

例子 1：计算数组元素的和（O(1) 空间复杂度）

def sum_array(arr):
    total = 0  # 常量空间
    for num in arr:
        total += num
    return total

• 输入空间：数组 arr 占用 O(n) 的空间。
• 算法空间：变量 total 是一个常数，所占空间是 O(1)。

总空间复杂度：由于算法只使用了固定数量的额外空间，因此该算法的空间复杂度是_O_(1)。

例子 2：复制一个数组（O(n) 空间复杂度）

def copy_array(arr):
    new_arr = arr.copy()  # 创建一个新的数组
    return new_arr

• 输入空间：数组 arr 占用 O(n) 的空间。
• 算法空间：新数组 new_arr 占用 O(n) 的空间。

总空间复杂度：算法创建了一个大小与输入数组相同的新数组，因此空间复杂度是 O(n)。

例子 3：递归计算斐波那契数列（O(n) 空间复杂度）

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

• 输入空间：只有一个整数 n，占用 O(1) 的空间。
• 递归栈空间：每次递归调用会占用栈空间，递归的最大深度为 n，因此递归栈的空间复杂度是 O(n)。

总空间复杂度：由于递归调用栈的深度为 n，因此空间复杂度是 O(n)。

空间复杂度与时间复杂度的关系

在分析算法时，时间复杂度和空间复杂度常常是互相影响的。

一般来说，某些算法为了提高时间效率可能需要消耗更多的空间，反之，空间有限的情况下也可能牺牲时间效率。

• 空间换时间：例如，使用更多的内存来存储中间结果，减少重复计算（例如，动态规划的备忘录方法）。
• 时间换空间：通过减少内存使用来降低空间消耗，可能需要通过更多的计算来弥补空间的不足。