快速排序的空间复杂度

Question

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

​

在图中，

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

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

在ant时间点上仅构成O(log )空间。那么复杂度变成O(n)了吗？

Answer 1

在上面给出的树示例中，您展示了一次快速排序，它总是在每一步中选择准确的中间元素作为拆分点。这使得递归深度为O(log )，因此，正如您所提到的，即使没有优化，空间使用量也将为O(log )。

但是，如果快速排序运行得不好，会发生什么呢？也就是说，如果总是选择数组中绝对最大或绝对最小的元素作为每个点的轴心点，会发生什么？那么您的递归树将如下所示：

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

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