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)堆栈空​​间.我也相信这个版本的最大可能堆栈空间应该是θ(n).

所以,在所有这些之后,我如何估计每个QuickSort版本的最小可能和最大可能的递归深度？我在上述推论中是对的吗？

提前致谢.

Answer 1

最糟糕的情况

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

最好的情况

在最偶然可能的分割中,PARTITION产生两个子问题,每个子问题的大小不超过n = 2,因为一个是大小为底(n/2),另一个是大小为(n/2)-1.在这种情况下,quicksort运行得更快.在这种情况下,递归树就是所谓的完整二叉树.它可以在最后一级h,尽可能地保留1到2h节点,然后h = log n,然后是quicksortθ(nlog n)的最佳情况行为,并且如您所见,在最佳情况下相应递归树的最后一级的数量是θ(log n).

结论

最小值:θ(log(n))

最大值:θ(n)