QuickSort Schätzung der Rekursionstiefe

Question

Als Rekursionstiefe die maximale Anzahl der aufeinanderfolgenden rekursiven Aufrufe vor QuickSort trifft seine Basis-Fall, und beachten Sie, dass es (Zufallsvariable) ist eine zufällige Variable, da es von der gewählten Drehpunkt abhängt.

Was ich möchte, ist die Schätzung der minimal möglichen und maximal möglichen Rekursionstiefe von QuickSort.

Das folgende Verfahren beschreibt die Art und Weise, das ist QuickSort normalerweise implementiert:

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 

Der zweite rekursiven Aufruf in QuickSort ist nicht wirklich notwendig; Dies kann durch Verwendung einer iterativen Kontrollstruktur vermieden werden. Diese Technik wird auch Endrekursion genannt, und es kann wie implementiert werden:

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

In dieser Version werden die Informationen für das letzte Gespräch ist an der Spitze des Stapels, und die Informationen für den ersten Anruf bei der Boden. Wenn eine Prozedur aufgerufen wird, werden ihre Informationen auf den Stapel geschoben. Wenn es beendet wird, werden seine Informationen abgerufen. Da ich davon ausgehe, dass Array-Parameter durch Zeiger dargestellt werden, benötigt die Information für jeden Prozeduraufruf auf dem Stapel O (1) Stapelspeicherplatz. Ich glaube auch, dass der maximal mögliche Stack-Platz bei dieser Version θ (n) sein sollte.

Also, wie kann ich nach all diesen Aussagen die minimal mögliche und maximal mögliche Rekursionstiefe jeder QuickSort-Version schätzen? Habe ich Recht in der obigen Schlussfolgerung?

Vielen Dank im Voraus.

Answer 1

Worst-Case

Das Worst-Case-Verhalten für quicksort tritt auf, wenn die Partitionierung Routine ein Teilproblem mit n erzeugt -1 Elementen und einen mit 0 Elementen Teilungskosten θ (n) Zeit. Wenn die Partitionierung auf jeder rekursiven Ebene des Algorithmus maximal unsymmetrisch ist, ist die Tiefe des Baums n und der Worst-Case ist θ (n) das Worst-Case-Verhalten für Quicksort θ (n^2), wie Sie die Zahl sehen der letzten Ebene des entsprechenden Rekursionsbaums ist im schlimmsten Fall θ (n).

Best-Case-

In dem am meisten sogar möglich, Split, produziert PARTITION zwei Teilprobleme, die jeweils Größe nicht mehr als n = 2, da eine Größe Etage (n/2) und eine der Größe Boden (n/2) -1. In diesem Fall läuft Quicksort viel schneller.Der Rekursionsbaum ist in diesem Fall der so genannte vollständige Binärbaum. Er kann zwischen 1 und 2h Knoten, so weit wie möglich links, auf der letzten Ebene h, dann h = log n, dann das Best-Case-Verhalten für Quicksort θ haben (nlog n), und wie Sie sehen, ist die Nummer der letzten Ebene des entsprechenden Rekursionsbaums im besten Fall θ (log n).

Fazit

Minimum: θ (log (n))

Maximum: θ (n)

Answer 2

Dies hängt sehr davon ab, wie Sie den Algorithmus codieren. Normalerweise wird nur der kleinere Teil mit einem rekursiven Aufruf ausgeführt, der größere Teil wird durch eine Iteration innerhalb derselben Inkarnation erledigt. Bei diesem Ansatz ist die maximale Tiefe log2 (N), die minimale Tiefe ist 1.

In jedem Schritt kann der kleinere Teil höchstens halb so groß sein wie der Bereich. Also im schlimmsten Fall benötigen Sie log2 (N) Schritte, um eine Größe von 1 zu erreichen.

Das andere Extrem ist, wenn der kleinere Teil immer nur Größe eins hat. In diesem Fall sind keine rekursiven Aufrufe erforderlich.