QuickSort估算递归深度 [英] QuickSort's estimation of recursion depth

问题描述

作为递归深度，QuickSort击中它的基本情况之前的连续递归调用的最大数量，并请注意，它（递归深度）是随机变量，因为它取决于所选的枢轴。

Being the recursion depth the maximum number of successive recursive calls before QuickSort hits it´s base case, and noting that it (recursion depth) is a random variable, since it depends on the chosen pivot.

我要估算的是QuickSort的最小可能和最大可能递归深度。

What I want is to estimate the minimum-possible and maximum-possible recursion depth of QuickSort.

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

The following procedure describes the way thats QuickSort is normally implemented:

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中的第二个递归调用并不是必需的；可以通过使用迭代控制结构来避免这种情况。此技术也称为尾递归，可以像以下那样实现：

The second recursive call in QuickSort is not really necessary; it can be avoided by using an iterative control structure. This technique is also called tail recursion, and it can be implemented like:

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）。

In this version, the information for the most recent call is at the top of the stack, and the information for the initial call is at the bottom. When a procedure is invoked, its information is pushed onto the stack; when it terminates, its information is popped. Since I assume that array parameters are represented by pointers, the information for each procedure call on the stack requires O(1) stack space. I also believe that the maximum-possible stack space with this version should be θ(n).

因此，在上述所有内容之后，我如何估算最小的-每个QuickSort版本的最大可能递归深度是多少？我在上面的推论中正确吗？

So, after all this said, how can I estimate the minimum-possible and maximum-possible recursion depth of each QuickSort version? Am I right in the above inference?

预先感谢。

推荐答案

最坏情况

当排序例程产生一个包含n -1个元素的子问题和一个包含n -1个元素的子问题时，发生quicksort的最坏情况。 0个元素。分区耗费时间（n）。如您所见，如果在算法的每个递归级别上分区最大程度地不平衡，则树的深度为n，最坏的情况是θ（n）quicksortthe（n ^ 2）的最坏情况

The worst-case behavior for quicksort occurs when the partitioning routine produces one subproblem with n -1 elements and one with 0 elements.The partitioning costs θ(n) time. If the partitioning is maximally unbalanced at every recursive level of the algorithm, then the depth of the tree is n and the worst case is θ(n) the worst-case behavior for quicksort θ(n^2), as you see the number of the last level of the corresponding recursion tree in the worst case is θ(n).

最佳情况

在最均匀的拆分中，PARTITION产生两个子问题，每个子问题的
大小不超过n = 2，因为一个子大小为floor（n / 2），而尺寸楼板（n / 2）-1之一。在这种情况下，快速排序的运行速度要快得多。在这种情况下，递归树就是所谓的完整二叉树。它可以在最后一级h处具有1到2h个节点，并尽可能远地位于左侧，然后h = log n，那么对于quicksortθ（nlog n），最好的情况是行为，并且如您所见，在最好的情况下，相应递归树的最后一级的数目是θ（log n）。

In the most even possible split, PARTITION produces two subproblems, each of size no more than n=2, since one is of size floor(n/2) and one of size floor(n/2) -1. In this case, quicksort runs much faster.The recursion tree in this case is what is known as complete binary tree It can have between 1 and 2h nodes, as far left as possible, at the last level h, then h = log n, then the best-case behavior for quicksort θ(nlog n), and as you see the number of the last level of the corresponding recursion tree in the best case is θ(log n).

结论

最低：θ（log（n））

Minimum: θ(log(n))

最大值：θ（n）

Maximum: θ(n)

这篇关于QuickSort估算递归深度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！