QuickSort对递归深度的估计

递归深度是 QuickSort 达到其基本情况之前连续递归调用的最大数量，并注意它（递归深度）是一个随机变量，因为它取决于所选的主元。

我想要的是估计快速排序的最小可能和最大可能递归深度。

以下过程描述了 QuickSort 通常实现的方式：

QUICKSORT(A,p,r)
    if p<r
        q ← PARTITION(A,p,r)
        QUICKSORT(A,p,q−1)
        QUICKSORT(A,q+1,r)
    return A

PARTITION(A,p,r)
    x←A[r]
    i←p−1
    for j ←p to r−1
        if A[j] ≤ x
            i ← i +1
            exchange A[i] ↔ A[j]
    exchange A[i +1] ↔ A[r]
    return i +1

QuickSort 中的第二次递归调用并不是真正必要的；可以通过使用迭代控制结构来避免这种情况。这种技术也称为尾递归，其实现方式如下：

QUICKSORT_tail(A,p,r)
    while p<r
        q ← PARTITION(A,p,r)
        QUICKSORT(A,p,q−1)
        p ← q+1
    return A

在此版本中，最近一次调用的信息位于堆栈顶部，初始调用的信息位于堆栈底部。当一个过程被调用时，它的信息被压入堆栈；当它终止时，它的信息被弹出。由于我假设数组参数由指针表示，因此堆栈上每个过程调用的信息都需要 O(1) 堆栈空间。我还相信这个版本的最大可能堆栈空间应该是 θ(n)。

那么，说了这么多，我如何估计每个 QuickSort 版本的最小可能和最大可能递归深度？我的上述推论正确吗？

提前致谢。

最坏的情况下

当分区例程产生一个包含 n -1 个元素的子问题和一个包含 0 个元素的子问题时，就会发生快速排序的最坏情况。分区花费 θ(n) 时间。如果分区在算法的每个递归级别上都最大程度地不平衡，则树的深度为 n，最坏情况为 θ(n)，快速排序的最坏情况行为为 θ(n^2)，如您所见最坏情况下相应递归树最后一层的值是θ(n)。

最好的情况

在最均匀的划分中，PARTITION 产生两个子问题，每个子问题 大小不超过n=2，因为一个的大小为floor(n/2)，另一个的大小为floor(n/2) -1。在这种情况下，快速排序运行得更快。这种情况下的递归树就是所谓的完全二叉树，它可以有 1 到 2h 个节点，尽可能左边，在最后一层 h，则 h = log n，那么快速排序的最佳情况行为为 θ(nlog n)，如您所见，最佳情况下相应递归树的最后一级的编号为 θ(log n)。

结论

最小值：θ(log(n))

最大值：θ(n)