最坏情况快速排序空间复杂性解释

Question

我想展示Quicksort空间复杂性的最坏情况。

我在想它，快速排序不使用辅助数组，它只是在分区子程序上创建一些辅助变量，但它只是操作数组中的项目。所以，很明显，我的结论是它使用了O（n）空间。

但我在网上搜索发现，Quicksort在最坏情况下的空间复杂度为O（logn）。

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

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），即分区总是不平衡的；例如，一个分区总是大小为k，另一个分区总是大小为n-k，其中k是常数（例如1、2或3），n是每轮递归中要分区的数组的大小。

换句话说，在最坏的情况下，在每一轮递归中，总是有一个大小的分区

如果在最坏的情况下，您可以递归O（log n）轮以获得空间复杂度，但需要O（n）轮来获得时间复杂度，这将是不合逻辑的。

Answer 2

如果像这样实现快速排序，那么最坏情况的空间复杂度是O（n）：

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

但快速排序的真正实现从来都不是这样写的。它们是这样写的：

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

正如@YvesDoust所说，重要的是在较小的部分递归，然后在较大的部分循环(或尾部递归，但这是另一个故事)。

这样，每次递归调用的范围最多是调用者范围的一半，最大深度是O(log n)

Answer 3

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

在直接的QuickSort中，分区每次都非常不利，只能将子阵列减少一个元素。因此，空间复杂度为O（n）！（通常是灾难）。

因此，首先对最小的子数组进行递归并使用尾递归很重要。这将最坏情况降低到O（Log n）。