概念定义

空间复杂度涉及的空间类型有：

输入空间： 存储输入数据所需的空间大小；

暂存空间： 算法运行过程中，存储所有中间变量和对象等数据所需的空间大小；

输出空间： 算法运行返回时，存储输出数据所需的空间大小；

通常情况下，空间复杂度指在输入数据大小为 N 时，算法运行所使用的「暂存空间」+「输出空间」的总体大小。

而根据不同来源，算法使用的内存空间分为三类：

指令空间：编译后，程序指令所使用的内存空间。

数据空间：算法中的各项变量使用的空间，包括：声明的常量、变量、动态数组、动态对象等使用的内存空间。

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None
def algorithm(N):
    num = N         # 变量
    nums = [0] * N  # 动态数组
    node = Node(N)  # 动态对象

栈帧空间：程序调用函数是基于栈实现的，函数在调用期间，占用常量大小的栈帧空间，直至返回后释放。如以下代码所示，在循环中调用函数，每轮调用 test() 返回后，栈帧空间已被释放，因此空间复杂度仍为 O(1) 。

def test():
    return 0
def algorithm(N):
    for _ in range(N):
        test()

算法中，栈帧空间的累计常出现于递归调用。如以下代码所示，通过递归调用，会同时存在 N 个未返回的函数 algorithm() ，此时累计使用 O(N) 大小的栈帧空间。

def algorithm(N):
    if N <= 1: return 1
    return algorithm(N - 1) + 1

符号表示

通常情况下，空间复杂度统计算法在 “最差情况” 下使用的空间大小，以体现算法运行所需预留的空间量，使用符号 O 表示。最差情况有两层含义，分别为「最差输入数据」、算法运行中的「最差运行点」。例如以下代码：

输入整数 N ，取值范围N≥1 ；

最差输入数据： 当 N≤10 时，数组 nums 的长度恒定为 10 ，空间复杂度为 O(10) = O(1)；当 N > 10 时，数组 nums 长度为 N ，空间复杂度为 O(N) ；因此，空间复杂度应为最差输入数据情况下的 O(N) 。

最差运行点： 在执行 nums = [0] * 10 时，算法仅使用 O(1) 大小的空间；而当执行 nums = [0] * N 时，算法使用 O(N) 的空间；因此，空间复杂度应为最差运行点的 O(N) 。

def algorithm(N):
    num = 5             # O(1)
    nums = [0] * 10     # O(1)
    if N > 10:
        nums = [0] * N  # O(N)

常见种类

根据从小到大排列，常见的算法空间复杂度有：

O(1) < O(log N) < O(N) < O(N^2) < O(2^N)

示例解析

对于以下所有示例，设输入数据大小为正整数 N ，节点类 Node 、函数 test() 如以下代码所示。

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None
# 函数 test()
def test():
    return 0

常数 O(1) ：普通常量、变量、对象、元素数量与输入数据大小 N 无关的集合，皆使用常数大小的空间。

def algorithm(N):
    num = 0
    nums = [0] * 10000
    node = Node(0)
    dic = { 0: '0' }

如以下代码所示，虽然函数 test() 调用了 N 次，但每轮调用后 test() 已返回，无累计栈帧空间使用，因此空间复杂度仍为 O(1) 。

def algorithm(N):
    for _ in range(N):
        test()

线性 O(N) ：元素数量与 N 呈线性关系的任意类型集合（常见于一维数组、链表、哈希表等），皆使用线性大小的空间。

def algorithm(N):
    nums_1 = [0] * N
    nums_2 = [0] * (N // 2)
    nodes = [Node(i) for i in range(N)]
    dic = {}
    
		for i in range(N):
        dic[i] = str(i)

如下图与代码所示，此递归调用期间，会同时存在 N个未返回的 algorithm() 函数，因此使用 O(N)大小的栈帧空间。

def algorithm(N):
    if N <= 1: return 1
    return algorithm(N - 1) + 1

平方 O(N^2)：元素数量与 N 呈平方关系的任意类型集合（常见于矩阵），皆使用平方大小的空间。

def algorithm(N):
    num_matrix = [[0 for j in range(N)] for i in range(N)]
    node_matrix = [[Node(j) for j in range(N)] for i in range(N)]

如下图与代码所示，递归调用时同时存在 N 个未返回的 algorithm() 函数，使用 O(N) 栈帧空间；每层递归函数中声明了数组，平均长度为N/2 ，使用 O(N) 空间；因此总体空间复杂度为 O(N^2)

def algorithm(N):
    if N <= 0: return 0
    nums = [0] * N
    return algorithm(N - 1)

指数 O(2^N) ：指数阶常见于二叉树、多叉树。例如，高度为 N 「满二叉树」的节点数量为 2^N ，占用 O(2^N)大小的空间；同理，高度为 N 的「满 m 叉树」的节点数量为 m^N ，占用 O(m^N) = O(2^N)大小的空间。

对数 O(\log N) ：对数阶常出现于分治算法的栈帧空间累计、数据类型转换等，例如：

快速排序 ，平均空间复杂度为 Θ(logN) ，最差空间复杂度为 O(N) 。拓展知识：通过应用 Tail Call Optimization ，可以将快速排序的最差空间复杂度限定至 O(N) 。

数字转化为字符串 ，设某正整数为 N ，则字符串的空间复杂度为 O(logN) 。推导如下：正整数 N 的位数为 log10 N，即转化的字符串长度为 log10 N ，因此空间复杂度为 O(logN) 。

时空权衡

对于算法的性能，需要从时间和空间的使用情况来综合评价。优良的算法应具备两个特性，即时间和空间复杂度皆较低。而实际上，对于某个算法问题，同时优化时间复杂度和空间复杂度是非常困难的。降低时间复杂度，往往是以提升空间复杂度为代价的，反之亦然。

由于当代计算机的内存充足，通常情况下，算法设计中一般会采取「空间换时间」的做法，即牺牲部分计算机存储空间，来提升算法的运行速度。

以 LeetCode 全站第一题 两数之和 为例，「暴力枚举」和「辅助哈希表」分别为「空间最优」和「时间最优」的两种算法。

方法一：暴力枚举

时间复杂度 O(N^2) ，空间复杂度 O(1)；属于「时间换空间」，虽然仅使用常数大小的额外空间，但运行速度过慢。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums) - 1):
            for j in range(i + 1, len(nums)):
                if nums[i] + nums[j] == target:
                    return i, j
        return

方法二：辅助哈希表

时间复杂度 O(N) ，空间复杂度 O(N) ；属于「空间换时间」，借助辅助哈希表 dic ，通过保存数组元素值与索引的映射来提升算法运行效率，是本题的最佳解法。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dic = {}
        for i in range(len(nums)):
            if target - nums[i] in dic:
                return dic[target - nums[i]], i
            dic[nums[i]] = i
        return []

作者：Krahets

链接：https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/r8ytog/

来源：力扣（LeetCode）

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。