一个排序算法如何具有O(1)的空间复杂度？

Question

10

我正在学习不同的排序算法以及它们的时间/空间复杂度。我看到像冒泡排序和插入排序这样的算法具有O(1)的空间复杂度，感觉很奇怪。

因为最低的空间复杂度应该是O(n)，即仅需要用于存储数据集本身的内存，而没有其他多余的内存吧？

- user5303592

2

排序可以是原地进行的，只使用固定数量的额外空间。一个例子是交换排序。 - Gordon Linoff

5

空间复杂度只关心排序所需的额外空间，而不涉及集合本身的存储空间。原地排序通常只需要在交换时为一个元素提供空间。 - user2390182

所测量的空间复杂度是操作所需的辅助空间量。输入和输出不计算在内，因为这不会增加太多信息并使讨论复杂化。 - Jeroen Mostert

啊，原来我一直搞混了。冒泡排序的空间复杂度为O(1)，因为每次比较的固定大小。 - user5303592

任何只使用固定数量的寄存器、标志、堆栈空间等算法，只要这些空间与输入无关，其空间复杂度都为O(1)。冒泡排序和插入排序显然符合此条件。 - Jeroen Mostert

2

我看到了一个针对这个问题的有趣的排序算法，从技术上讲是有效的。对于集合中的任何元素X，执行sleep(X);print(X)操作。使用多线程同时启动所有元素。这是一个相当不错的O(1)排序算法，尽管速度非常慢。 - Albert Renshaw

3个回答

7

一种排序算法的空间复杂度为O(1)，通过分配恒定数量的空间，例如用于迭代的几个变量等，它们与输入大小无关。

大多数归并排序的实现分配辅助数组，使其空间复杂度不是O(1)，而是O(n)。快速排序在理论上看起来像O(1)，但调用堆栈也算作空间，因此它被认为是O(log n)。

具有O(1)空间复杂度的排序算法示例包括：选择排序、插入排序、希尔排序和堆排序。

- arboreal84

1

不要忘记冒泡排序。 - Codor

1

冒泡排序具有二次时间复杂度，除了在学术环境中，它从未被使用过。 - arboreal84

你说得没错，但这不是我的重点。它具有恒定的空间复杂度，多项式运行时间，并且是人们最初会想到的第一个算法。 - Codor

很好将其作为一个众所周知的算法提出来，因为这个网站的许多读者可能已经听说过它，但是如果说它是人们最初想到的第一个算法，我不太确定。也许有些人会这么认为。这将是一项有趣的研究，想想看.... :) - Ray Toal

我认为选择排序和插入排序更适合介绍排序的概念。但这是个人偏好的问题。 - arboreal84

1

Bottom-up归并排序可以这样写，它只使用恒定的额外空间。这是渐进最优排序（O(n*log(n))），同时仅使用O(1)空间。

编辑：这个答案有点粗心。从底部向上的归并排序仅在链表上使用O(1)空间。对于在数组上使用O(1)空间的排序，堆排序是最好的选择。通过将数组原地转换为最大堆，然后重复调用delete-max，值被存储在数组的末尾。当堆为空时，数组已经排序完毕。

- Asad-ullah Khan

虽然这是正确的，但它并没有直接回答在这里发布的问题。也许这应该是一条评论？ - templatetypedef

我认为你是对的，可能我在这件事上有些草率了。我只是惊讶地发现没有人提到其中几个最优的O(1)排序算法。 - Asad-ullah Khan

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- gdelab · Accepted Answer

空间复杂度实际上是算法所使用的额外空间复杂度，即除了数据初始占用的空间之外需要的额外空间。冒泡排序和插入排序除了原始数据之外，只使用恒定的额外空间，因此它们的空间复杂度为O(1)。