空间复杂度的定义

Question

通过时间复杂度，我们将算法的运行时间理解为输入大小（表示内存中实例所需的位数）的函数。那么，关于这一观察，我们如何定义空间的复杂性呢？它显然与实例的大小无关...

Answer 1

可以通过多种方式定义空间复杂度，但是通常的定义如下。我们假定输入存储在某处的只读存储器中，有一个专用的只写存储器用于存储操作结果，并且有一些通用的“暂存空间”存储器用于进行辅助计算。通常，空间复杂度是存储输出以及所有暂存空间所需的空间量。例如，二进制搜索的空间复杂度为O（1），因为只需要O（1）存储空间即可存储输入和输出（假设数组索引适合机器字）。

有时，输入和输出空间会合并到一个存储单元中，并且可以修改输入。例如，在此模型中，堆排序的空间复杂度为O（1），而合并排序的空间复杂度为O（n），用于合并所需的辅助存储空间。

希望这可以帮助！