space 复杂度的定义
Definition of space complexity
通过时间复杂度，我们将算法的 运行 时间理解为输入大小（表示内存中的实例所需的位数）的函数。那么关于这个观察，我们如何定义 space 复杂性？显然跟实例的大小关系不大...
Space复杂性可以用多种方式定义，但通常的定义如下。我们假设输入存储在某个地方的只读存储器中，有一个专门的只写存储器用于存储操作的结果，并且有一些通用的 "scratch space" 存储器用于进行辅助计算。通常，space 复杂度是存储输出和所有临时 space 所需的 space 数量。例如，二进制搜索具有 space 复杂度 O(1)，因为只需要 O(1) 存储 space 来存储输入和输出（假设数组索引适合机器字）。
有时，输入和输出space合并为一个存储单元，输入可以修改。例如，在此模型中，heapsort 具有 space 复杂度 O(1)，而 mergesort 具有 space 复杂度 O(n) 用于合并所需的辅助存储 space。
希望对您有所帮助！
通过时间复杂度，我们将算法的 运行 时间理解为输入大小（表示内存中的实例所需的位数）的函数。那么关于这个观察，我们如何定义 space 复杂性？显然跟实例的大小关系不大...
Space复杂性可以用多种方式定义，但通常的定义如下。我们假设输入存储在某个地方的只读存储器中，有一个专门的只写存储器用于存储操作的结果，并且有一些通用的 "scratch space" 存储器用于进行辅助计算。通常，space 复杂度是存储输出和所有临时 space 所需的 space 数量。例如，二进制搜索具有 space 复杂度 O(1)，因为只需要 O(1) 存储 space 来存储输入和输出（假设数组索引适合机器字）。
有时，输入和输出space合并为一个存储单元，输入可以修改。例如，在此模型中，heapsort 具有 space 复杂度 O(1)，而 mergesort 具有 space 复杂度 O(n) 用于合并所需的辅助存储 space。
希望对您有所帮助！