堆栈升序排序(空间分析)

Question

我正在阅读《破解编码面试》一书，遇到了一个问题：“编写一个程序，按升序对堆栈进行排序。您可以使用其他堆栈来保存项目，但不能将元素复制到任何其他数据结构（如数组）中。堆栈支持以下操作：push、pop、peek、isEmpty。”

这本书用O(n^2的时间复杂度和空间复杂度给出了答案。

但是，我偶然发现了这个博客，它使用快速排序方法在O（n log n）时间复杂性中提供了答案。

我想知道的是空间复杂度是O（n^2）吗？因为对该方法的每次调用都涉及初始化另外两个堆栈，以及另外两个递归调用。

我对空间复杂性仍然有点摇摇欲坠。我不确定这是否是 O（n^2） 空间，每个递归调用生成的新堆栈都小于升级的堆栈。

如果有人能在他们的答案后面解释一下，那就太好了。

Answer 1

在这种快速排序方法中，空间复杂度将完全遵循时间复杂度——原因很简单。递归地划分子堆栈(使用pivot ),直到每个元素都在一个大小为1的堆栈中。这导致(2^x = n)划分x个子栈(深度为log n ),最后你有n个栈，每个栈的大小为1。因此，总的空间复杂度将是O(n*log n)。

请记住，在这种情况下，空间复杂度将遵循时间复杂度，就像我们在每次迭代中占用新空间一样。所以，在最坏的情况下，空间复杂度将是O（n^2）。

Answer 2

平均情况下空间复杂度也是O（n log n）。如果空间复杂度恰好是O（n^2），那么时间复杂度怎么可能是O（n log n），因为每个分配的空间至少需要一次访问。

因此，在一般情况下，假设堆栈每次都被分成两半，在第I个递归深度，数组的大小变成O(n/2^{^}i，2^{^}i递归在第I个深度分支。因此，在第I个深度上分配的总大小是O(n/2^i) *2^{^}i = O(n)。

由于最大深度为logn，所以总体空间复杂度为O（nlogn）。

然而，在最坏的情况下，空间复杂度为O（n^2）。