这篇维基百科文章http://en.wikipedia.org/wiki/Quicksort#In-place_version表明 O(logn) 是就地排序的空间时间复杂度和http://futur3googl3r.blogspot.com/2008/08/ google-interview-questions.html这个采访网站建议它是 O(n)。我认为答案是 O(n) 但想知道我是否正确。
问问题
20310 次
2 回答
13
在这两篇文章中，他们所指的空间复杂度是额外空间（不包括存储原始数组所需的空间）。除了声明额外数组的常见情况外，这个额外的空间可能来自调用堆栈。每次递归调用都会在调用栈上创建一个栈帧，占用空间，栈帧的个数取决于输入大小n，所以需要统计。
让我们使用 Wikipedia 文章作为参考，因为正如 @Jim Mischel 所指出的那样，该博客非常不一致。
对于就地快速排序，从天真的实现进行修改将平均提供O(log n) 额外的空间，而不是天真的实现中的额外空间（在所有情况下）。正如博客1正确指出的那样，额外空间的最坏情况复杂性是，当算法遇到其最坏情况时（排序列表；将存在递归调用，因此调用堆栈将占用额外空间）。O(n) O(n)nO(n)
1：（感谢@rici 指出）但是，博主只有在我们假设没有维基百科文章中提到的优化的实现时才是正确的。通过首先在较小的部分上递归并为较长的部分实现尾部调用，可以改进算法以在最坏的情况下使用O(log n) 额外的空间。由于较小的部分总是小于输入大小的一半，因此最多会有O(log n)递归调用。假设完成了尾调用优化，较长的部分将重用当前堆栈帧，而不会产生额外的空间。如果没有进行尾调用优化，我们总是可以编写一个带有显式堆栈的迭代实现。
于 2013-02-22T23:35:04.183 回答
0
这次采访表明它是 O(n)
不，它不会：
解决方案：快速排序的空间复杂度为 O(logn)，即使在最坏的情况下也是如此。
于 2013-02-22T23:24:53.777 回答