快速排序的空间复杂性

Question

我已经了解到,没有Sedgewick消除尾递归的技巧,快速排序的空间复杂度是O(n).但是如果我们跟踪存储的堆栈上的调用,则在任何调用时都是O(log n)步骤,如图所示.

在图中,

在计算(1,1)的值时,我们存储[(1,8),(1,4),(1,2)]的调用,

在计算(3,3)的值时,我们存储[(1,8),(1,4),(3,4)]的调用等等

在蚂蚁时间点仅构成O(log n)空间.然后复杂性变成O(n)？

Answer 1

在上面给出的树示例中,您展示了一系列快速排序,总是碰巧选择精确的中间元素作为每一步的分裂点.这使得递归深度为O(log n),因此,正如您所指出的,即使没有优化,空间使用也将是O(log n).

但是如果你得到一个糟糕的快速排序会发生什么？也就是说,如果你总是选择阵列的绝对最大或绝对最小元素作为每个点的枢轴,会发生什么？然后你的递归树看起来像这样:

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

现在你的递归树有高度Θ(n),所以如果实现没有任何尾调用消除quicksort将使用Θ(n)空间,每个点的每个活动递归调用一个.