空间复杂度的定义 [英] Definition of space complexity

问题描述

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

By time complexity we understand algorithm's running time as a function of the size of input (number of bits needed to represent the instance in memory). Then how do we define space complexity, with regard to this observation? It obviously can't be related to the size of instance...

推荐答案

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

Space complexity can be defined in multiple ways, but the usual definition is the following. We assume that the input is stored in read-only memory somewhere, that there is a dedicated write-only memory for storing the result of the operation, and that there is some general "scratch space" memory for doing auxiliary computations. Typically, space complexity is the amount of space needed to store the output and for all the scratch space. For example, binary search has space complexity O(1) because only O(1) storage space is needed to store the input and output (assuming that array indices fit into machine words).

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

Sometimes, the input and output space are combined into a single storage unit and the input can be modified. In this model, for example, heapsort has space complexity O(1), while mergesort has space complexity O(n) for the auxiliary storage space needed for the merging.

希望这会有所帮助！

这篇关于空间复杂度的定义的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！