快速排序的空间复杂度 [英] Space Complexity of Quick Sort

问题描述

我了解到，没有Sedgewick消除尾部递归技巧的快速排序的空间复杂度为O（n）。但是，如果我们跟踪存储在堆栈上的调用，则在任何调用处都是O（log n）步骤，如图所示。

I have learnt that the space complexity of quick sort without Sedgewick's trick of eliminating tail recursion is O(n). But if we trace the calls on the stack that are stored, it is O(log n) steps at any call as shown in the figure.

在图中，

计算（1,1）的值时，我们存储[[1,8），（1,4），（1,2）]的调用，

while calculating the value of (1,1) we store the calls of [(1,8), (1,4), (1,2)] ,

计算（3,3）的值，我们存储了[[1,8），（1,4），（3,4）]的调用，依此类推

while calculating the value of (3,3) we store the calls of [(1,8), (1,4), (3,4)] and so on

在蚂蚁时间点仅构成O（log n）空间。那么复杂度是否变为O（n）？

which constitute for only O(log n) space at ant point of time. Then does the complexity become O(n) ?

推荐答案

在上面给出的树示例中，您展示了一系列快速排序，总是碰巧在每一步都选择精确的中值元素作为分割点。如前所述，这使得递归深度为O（log n），因此即使不进行优化，空间使用量也将为O（log n）。

In the tree example you gave above, you showed a run of quicksort that always happens to pick the exact median element as the splitting point at each step. That makes the recursion depth O(log n) and so, as you noted, the space usage would be O(log n) even without the optimization.

但是会发生什么如果您在快速排序方面遇到问题？也就是说，如果始终选择数组中绝对最大或绝对最小的元素作为每个点的支点，会发生什么？然后您的递归树将如下所示：

But what happens if you get a bad run of quicksort? That is, what happens if you always pick the absolute biggest or absolute smallest element of the array as the pivot at each point? Then your recursion tree will look something like this:

    size n
       \
       size n-1
         \
         size n-2
           \
            ...
             \
              1

现在您的递归树的高度为Θ（n），因此，如果在没有任何尾调用消除的情况下实施，快速排序将使用Θ（n）空间，每活动一个递归调用。

Now your recursion tree has height Θ(n), so if implemented without any tail call elimination quicksort will use Θ(n) space, one per active recursive call at each point.

这篇关于快速排序的空间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！