algorithm - 最坏情况Quicksort空间复杂性说明

我想展示最快情况下的快速排序空间复杂度。
我正在考虑它，QuestS排序不使用辅助数组，它只是在分区子例程上创建了一些辅助变量，但它只是操纵数组中的项。显然，我的结论是，它使用了O（n）空间。
但是在互联网上搜索，我发现Quicksort在最坏情况下的空间复杂度是O（log n）。
我只是不明白为什么在最坏的情况下它比输入数组占用更少的空间？
注：我在看《算法导论》这本书。
我已经试过计算算法中所有变量的声明数。

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

最佳答案

在评估空间复杂度时，不计算输入存储，而是计算堆栈深度。
在直接快速排序中，分区每次都可能非常不利，并且只将子数组减少一个元素。因此，空间复杂度为O（n）！（通常是灾难性的）。
因此，首先在最小子阵上递归并使用尾部递归是很重要的。这将最坏的情况降低到O（Log n）。

关于algorithm - 最坏情况Quicksort空间复杂性说明，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/57860776/