不同排序算法的空间复杂度差异

Question

我正在尝试理解不同排序算法的空间复杂度。

从上面的链接http://bigocheatsheet.com/?goback=.gde_98713_member_241501229中，我发现冒泡排序、插入排序和选择排序的复杂度为O(1)，而快速排序的复杂度为O(log(n))，合并排序的复杂度为O(n)。

我们实际上没有在任何算法中分配额外的内存。那么，为什么当我们使用相同的数组对它们进行排序时，空间复杂度会有所不同呢？

- Naveen

Answer 1

当你运行代码时，内存分配有两种方式：

1. 隐式地，在设置函数调用时。

2. 显式地，当你创建内存块时。

快速排序是隐式使用内存的一个好例子。在进行快速排序时，最坏情况下我会递归调用自己O(n)次，在平均情况下递归调用自己O(log(n))次。这些递归调用每次需要 O(1) 的空间来跟踪，导致最坏情况下复杂度为 O(n)，平均情况下为 O(log(n))。

归并排序是显示使用内存的一个好例子。我需要获取两个已经排好序的数据块，并创建一个位置来放置合并后的结果，然后将两个数据块中的数据合并到这个位置上。创建存放合并结果的位置需要 O(n) 的数据。

要将空间复杂度降至 O(1)，你需要不分配内存，并且不递归调用自己。这对于所有的冒泡排序、插入排序和选择排序都是成立的。

- btilly

Answer 2

重要的是要记住，实现这些算法有很多不同的方法，每种不同的实现都有不同的空间复杂度。

让我们从归并排序开始。数组上最常见的归并排序实现方式是通过分配外部缓冲区来执行各个范围的合并。这需要空间来容纳数组的所有元素，这需要额外的空间Θ(n)。但是，您可以选择为每个合并使用原地合并，这意味着您只需要为递归调用的堆栈帧留出额外的空间，将空间复杂度降至Θ(log n)，但会增加算法的运行时间。您还可以使用原地合并进行自底向上的归并排序，这仅需要O(1)的额外空间，但具有更高的常数因子。

另一方面，如果您正在对链表进行归并排序，则空间复杂度将大不相同。您可以在空间O(1)中合并链接列表，因为元素本身可以轻松地重新连接。这意味着归并排序链接列表的空间复杂度是Θ(log n)，需要存储递归调用的堆栈帧所需的空间。

让我们以快速排序为例。 快速排序通常不会分配任何外部内存，但它确实需要空间来存储它使用的堆栈帧。 如果枢轴始终是数组中最大或最小的元素，则快速排序的朴素实现在最坏情况下可能需要Θ（n）的堆栈帧空间，因为在这种情况下，您将在大小为n-1、n-2、n-3等的数组上递归调用函数。 然而，有一个标准优化可以执行，即本质上是尾调用消除：您在数组的两个半部分中较小的那一半上递归调用快速排序，然后重用当前调用的堆栈空间来处理较大的那一半。 这意味着您只为大小最多为n / 2、n / 4、n / 8等的子数组进行递归调用时分配新内存，因此空间使用量降至O（log n）。

- templatetypedef

Answer 3

我假设我们要排序的数组是通过引用传递的，并且我假设数组的空间不计入空间复杂度分析。

通过巧妙的实现，快速排序的空间复杂度可以达到O(n)（随机化快速排序的期望为O(log n)），例如：不要复制整个子数组，而只需传递索引。

快速排序的O(n)来自于“嵌套”递归调用的数量可能为O(n)的事实：想象一下如果您在选择枢轴时一直做出不幸的选择会发生什么。虽然每个堆栈帧占用O(1)的空间，但可能有O(n)个堆栈帧。如果我们谈论随机化快速排序，则期望深度（即期望堆栈空间）为O(log n)。

对于归并排序，我预计空间复杂度为O(log n)，因为您最多进行O(log n)个“嵌套”递归调用。

你引用的结果也包括数组占用的空间：因此归并排序的时间复杂度为O(log n)（栈空间）加上O(n)（数组），这意味着总空间复杂度为O(n)。对于快速排序，它是O(n)+O(n)=O(n)。

- blazs