algorithm - 最坏情况快速排序空间复杂度解释

Question

我想展示快速排序空间复杂度的最坏情况。

我在考虑它，Quicksort 不使用辅助数组，它只是在 Partition 子例程上创建一些辅助变量，但它只是操纵数组中的项目。所以，很明显，我的结论是它使用了 O(n) 空间。

但是在互联网上搜索我发现在最坏情况下快速排序的空间复杂度是 O(log n)。

我只是不明白为什么在最坏的情况下它比输入数组占用更少的空间？

ps.：我正在关注“算法简介”的书。

我已经尝试过计算算法上的所有变量声明。

QUICKSORT(A, p, r)
    if p < r
        q = partition(A, p, r)
        QUICKSORT(A, p, q - 1)
        QUICKSORT(A, q + 1, r)


PARTITION(A, p, r)
    x = A[r] // pivot
    i = p - 1
    for j = p to r - 1
        if A[j] <= x
            i = i + 1
            exchange A[i] with A[j]
    exchange A[i + 1] with A[r]
    return i + 1

标签： algorithmsortingquicksort

Answer 1

在评估空间复杂度时，您不计算输入存储，但计算堆栈深度。

在直接快速排序中，每次分区都可能非常不利，并且只会将子数组减少一个元素。因此，空间复杂度为O(n)！（通常是灾难）。

出于这个原因，首先在最小子数组上递归并使用尾递归很重要。这将最坏的情况降低到O(Log n)。