就地快速排序的空间复杂度为O(n)或O(logn)。

Question

这篇维基百科文章建议使用原地排序的空间时间复杂度为O(logn)http://en.wikipedia.org/wiki/Quicksort#In-place_version，而这个面试网站建议它是O(n)http://futur3googl3r.blogspot.com/2008/08/google-interview-questions.html。我认为答案是O(n)，但想知道我是否正确。

- vkaul11

---

它们两个可能描述了相同的算法（我没有深入细节）。O(n) 额外空间是最坏情况，而O(log n) 额外空间则是平均情况。 - nhahtdh

Answer 1

在这两篇文章中，他们所提到的空间复杂度是指额外的空间（不包括存储原始数组所需的空间）。这个额外的空间可能来自于调用堆栈，除了通常情况下声明额外数组的情况。每次递归调用都会在调用堆栈上创建一个堆栈帧，占据空间，而堆栈帧的数量取决于输入大小n，因此需要计算。

让我们以维基百科文章为参考，因为博客的一致性很差，正如@Jim Mischel所指出的那样。

对于原地快速排序，从朴素实现进行修改将平均给出O(log n) 额外的空间，而不是朴素实现中的O(n) 额外的空间（在所有情况下都是如此）。正如博客¹正确指出的那样，当算法遇到其最坏情况（排序列表）时，额外空间的最坏复杂度是O(n)，因为会有n个递归调用，所以调用堆栈将占用O(n) 额外的空间。

¹: （感谢@rici指出）然而，只有在我们假设没有进行Wikipedia文章中提到的优化的情况下，博主才是正确的。可以通过先递归较小部分并为较长部分实现尾调用来改进算法，以在最坏情况下使用O(log n) 额外空间。由于较小部分始终小于输入大小的一半，因此最多会有O(log n)次递归调用。假设已经完成了尾调用优化，则较长部分将重复使用当前堆栈帧而不产生额外空间。如果没有进行尾调用优化，我们总是可以编写具有显式堆栈的迭代实现。

- nhahtdh

---

那篇博客的第一段是自相矛盾的。它正确地指出最坏情况下是O(log n)递归调用，但接着又说它可以进行O(n)嵌套递归调用。到底是哪一个呢？而第二段则离题太远，难以理解。 - Jim Mischel

@vkaul11：关键在于，如果您总是首先对较短的分区进行递归，那么嵌套递归调用的数量就是o(log n)，因为较短的分区小于总分区大小的一半。尾递归不是嵌套调用，因此博主是错误的（我也不相信他是谷歌员工）。 - rici

@rici：无论如何，我已经修改了帖子，以便正确地解决了O(log n)的问题，而不是简单地说它是最坏情况下的O(n)。 - nhahtdh

@vkaul11：我已经编辑了我的帖子。博主并不知道可以进行哪些实现优化来改善算法的复杂度。 - nhahtdh

@nhahtdh：你不需要编译器的任何帮助；你可以自己将尾递归重写为循环。不需要显式栈。但是，请注意，Hoare原始的快速排序算法确实使用了显式栈，并且他仔细描述了如何确保显式栈可以预先分配log2(n)个插槽。 - rici

Answer 2

这个访谈表明它是O(n)。

不，它并不是：

解决方案：快速排序的空间复杂度为O(logn)，即使在最坏的情况下也是如此。

- user529758

---

它取决于算法的实现。正如维基百科文章所解释的那样，有两种实现方法，您可以使用O(n)空间进行简单实现，也可以使用仅需O(logn)空间的更好实现方法。 - Techmonk

完整的快速排序解决方案采用原地分区，使得在进行任何递归调用之前仅使用恒定的额外空间。然而，如果它已经进行了O(logn)个嵌套递归调用，则需要从每个递归调用中存储恒定数量的信息。由于最佳情况下最多进行O(logn)个嵌套递归调用，因此它使用O(logn)的空间。最坏情况下进行O(n)个嵌套递归调用，因此需要O(n)的空间。请参见我发布的链接：http://futur3googl3r.blogspot.com/2008/08/google-interview-questions.html - vkaul11

@Techmonk 这篇文章也提到了“当小心实施时” :) - user529758

H2CO3，你至少可以解释一下为什么最坏情况的时间复杂度不是O(n)，而是O(logn)，而不是只是说它是这样的。 - vkaul11