QuickSort stima della profondità di ricorsione

Question

Essendo la profondità di ricorsione il numero massimo di chiamate ricorsive successive prima che QuickSort colpisca il suo caso base, e notando che esso (profondità di ricorsione) è una variabile casuale, poiché dipende dal pivot scelto.

Quello che voglio è quello di stimare la profondità minima-possibile e massima possibile ricorsione di QuickSort.

La procedura seguente descrive il modo in cui questo è QuickSort viene normalmente attuato:

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 

La seconda chiamata ricorsiva in QuickSort non è realmente necessario; può essere evitato usando una struttura di controllo iterativa. Questa tecnica è chiamata anche coda ricorsione, e può essere implementato come:

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

In questa versione, le informazioni per la chiamata più recente è in cima alla pila, e le informazioni per la chiamata iniziale è il fondo. Quando viene invocata una procedura, le sue informazioni vengono inserite nello stack; quando termina, le sue informazioni sono spuntate. Poiché presumo che i parametri dell'array siano rappresentati da puntatori, le informazioni per ogni chiamata di procedura nello stack richiedono O (1) spazio di stack. Credo inoltre che lo spazio di stack massimo possibile con questa versione dovrebbe essere θ (n).

Quindi, dopo tutto questo, ha detto, come posso stimare la profondità minima-possibile e massima possibile ricorsione di ciascuna versione QuickSort? Ho ragione nell'inferenza di cui sopra?

Grazie in anticipo.

Answer 1

caso peggiore

Il comportamento peggiore per Quicksort si verifica quando la routine di partizionamento produce un sottoproblema con n -1 elementi e uno con 0 elements.The costi partizionamento θ (n). Se il partizionamento è massimamente sbilanciato ad ogni livello ricorsivo dell'algoritmo, quindi la profondità dell'albero è n e il caso peggiore è θ (n) il comportamento peggiore per quicksort θ (n^2), come si vede il numero l'ultimo livello dell'albero di ricorsione corrispondente nel caso peggiore è θ (n).

caso migliore

Nella scissione più uniforme possibile, PARTITION produce due sottoproblemi, ciascuno dei dimensioni non più di n = 2, dal momento che uno è di piano dimensione (n/2) e una delle dimensione piano (n/2) -1. In questo caso, quicksort viene eseguito molto più velocemente.L'albero di ricorsione in questo caso è ciò che è noto come albero binario completo Può avere tra 1 e 2 h nodi, il più a sinistra possibile, all'ultimo livello h, quindi h = log n, quindi il comportamento migliore per quicksort θ (nlog n), e come vedi il numero dell'ultimo livello dell'albero di ricorsione corrispondente nel migliore dei casi è θ (log n).

Conclusione

minima: θ (log (n))

massima: θ (n)

Answer 2

Questo dipende molto da come si codifica l'algoritmo. Di solito, solo la parte più piccola viene eseguita con una chiamata ricorsiva, la parte più grande viene eseguita da un'iterazione all'interno della stessa incarnazione. Con questo approccio, la profondità massima è log2 (N), la profondità minima è 1.

In ogni fase la parte più piccola può essere al massimo la metà dell'intervallo. Quindi, nel caso peggiore è necessario log2 (N) passi per raggiungere una dimensione di 1.

L'altro estremo è quando la parte più piccola ha sempre e solo una dimensione. In questo caso non sono necessarie chiamate ricorsive.