Ocena głębokości rekursji przez QuickSorta

Question

Jako głębokość rekurencji, maksymalna liczba kolejnych rekursywnych wywołań, zanim QuickSort trafi w jego bazę bazową, i zauważając, że jest to zmienna losowa, ponieważ zależy od wybranego przestawu.

To, czego chcę, to oszacowanie minimalnej możliwej i maksymalnej możliwej głębokości rekursji QuickSort.

Poniższa procedura opisuje sposób ów QuickSort zazwyczaj realizowane:

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 

Drugie wywołanie rekurencyjne w Quicksort nie jest to naprawdę konieczne; można tego uniknąć, stosując iteracyjną strukturę kontrolną. Technika ta nazywana jest także ogon rekurencji, a to może być realizowane następująco:

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

W tej wersji, informacje o ostatniej rozmowy jest na górze stosu, a informacja o wstępnej rozmowy jest dół. Gdy procedura jest wywoływana, jej informacje są przesyłane na stos; kiedy się kończy, jego informacje zostają zerwane. Ponieważ zakładam, że parametry tablicy są reprezentowane przez wskaźniki, informacja o każdym wywołaniu procedury na stosie wymaga przestrzeni stosu O (1). Uważam także, że maksymalna możliwa przestrzeń stosu w tej wersji powinna być θ (n).

Po tym wszystkim, jak mogę oszacować minimalną możliwą i maksymalną możliwą głębokość rekursji każdej wersji QuickSort? Czy mam rację w powyższym wnioskowaniu?

Z góry dziękuję.

Answer 1

najgorszego przypadku

Najgorszym zachowanie dla quicksort występuje, gdy rutynowe podział tworzy jeden subproblem zn -1 elementu i jeden z 0 elements.The kosztów przegród θ (n). Jeśli partycja jest maksymalnie niezbalansowana na każdym rekurencyjnym poziomie algorytmu, to głębokość drzewa wynosi n, a najgorszy przypadek to θ (n) najgorszy przypadek dla quicksorta θ (n^2), jak widzisz numer ostatniego poziomu odpowiedniego drzewa rekursji w najgorszym przypadku to θ (n).

najlepszym przypadku

W najbardziej nawet możliwe split Partycja wytwarza dwa podproblemów, z których każdy wielkości nie więcej niż n = 2, ponieważ jeden jest powierzchnia piętra (n/2) i jeden z wielkość podłogi (n/2) -1. W takim przypadku quicksort działa znacznie szybciej.Drzewo rekursji w tym przypadku jest znane jako pełne drzewo binarne Może zawierać od 1 do 2h węzłów, tak daleko jak to możliwe, na ostatnim poziomie h, następnie h = log n, a następnie zachowanie najlepszego przypadku dla quicksorta θ (nlog n), a jak widzisz, numer ostatniego poziomu odpowiedniego drzewa rekursji w najlepszym przypadku to θ (log n).

Wnioski

Minimum: θ (log (n))

maksymalna: θ (n)

Answer 2

To zależy w dużym stopniu od sposobu kodowania algorytmu. Zwykle tylko mniejsza część jest wykonywana z wywołaniem rekursywnym, większa część jest wykonywana przez iterację w ramach tego samego wcielenia. W tym podejściu maksymalna głębokość to log2 (N), minimalna głębokość to 1.

W każdym kroku mniejsza część może być co najwyżej o połowę mniejsza od zakresu. Tak więc w najgorszym przypadku potrzebujesz kroków log2 (N), aby osiągnąć rozmiar 1.

Drugą skrajnością jest sytuacja, w której mniejsza część ma zawsze tylko rozmiar jeden. W takim przypadku nie są potrzebne żadne rekursywne połączenia.