QuickSort对递归深度的估计

Question

作为递归深度，在 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)栈space。我也相信这个版本的最大可能堆栈 space 应该是 θ(n).

所以，说了这么多，我如何估计每个 QuickSort 版本的最小可能和最大可能递归深度？我上面的推断对吗？

提前致谢。

Answer 1

这在很大程度上取决于您如何编写算法代码。通常，只有较小的部分是通过递归调用完成的，较大的部分是通过同一化身中的迭代完成的。使用这种方法，最大深度为 log2(N)，最小深度为 1.

在每一步中，较小的部分最多可以是范围大小的一半。因此，在最坏的情况下，您需要 log2(N) 步才能达到 1 的大小。

另一个极端是较小的部分总是只有一号。在这种情况下，不需要递归调用。

Answer 2

最坏情况

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

最佳情况

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

结论

最小值：θ(log(n))

最大值：θ(n)

QuickSort对递归深度的估计

QuickSort's estimation of recursion depth

algorithm

recursion

quicksort