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

Question

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

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

但是在网上搜索我发现Quicksort在最坏情况下的空间复杂度是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

Answer 1

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

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

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