Dimostrare il tempo di esecuzione di Mergesort ottimizzato è Theta (nk + nlog (n/k))?

Question

Ok, so che Mergesort ha un tempo peggiore di Theta (NLOGN) ma il suo sovraccarico è alto e si manifesta vicino al fondo dell'albero di ricorsione in cui sono fatte le fusioni. Qualcuno ha proposto di fermare la ricorsione una volta che le dimensioni raggiungono K e passiamo all'ordinamento di inserimento a quel punto. Devo dimostrare che il tempo di esecuzione di questa relazione di ricorrenza modificata è Theta (NK + Nlog (N/K))? Sto spalancando su come affrontare questo problema ..

Answer 1

Forse un buon inizio è guardare la relazione di ricorrenza per questo problema. Immagino che per Mergesort tipico sembrerebbe qualcosa di simile:

T(N) = 2 * T(N / 2) + N

cioè stai dividendo il problema in 2 sottoproblemi della metà delle dimensioni e poi eseguendo n lavoro (l'iscrizione). Abbiamo un caso di base che richiede tempo costante.

Modellare questo come un albero che abbiamo:

T(N)   =   N   ->   T(N / 2)   
               ->   T(N / 2)

       =   N   ->   (N / 2)   ->   T(N / 4)
                              ->   T(N / 4)
               ->   (N / 2)   ->   T(N / 4)
                              ->   T(N / 4)

Questo dà un'espansione di

T(N) = N + 2N/2 + 4N/4 + ...
     = N + N + N ...

Quindi davvero dobbiamo solo vedere quanto va in profondità. Sappiamo che il iIl livello th opera su sottoproblemi N / 2^i in misura. Quindi i nostri nodi foglia (T(1)) si verificano a livello L dove N / 2^L = 1:

N / 2^L = 1
N = 2^L
log N = log(2^L)
log N = L

Quindi il nostro runtime è N log N.

Ora introduciamo il tipo di inserimento. Il nostro albero assomigliarà a questo

T(N) = ... -> I(K)
           -> I(K)
             ...x N/K

In altre parole, lo faremo ad un certo livello L devo risolvere N/K Inserimento di ordinamento problemi di dimensioni K. L'ordinamento di inserzione ha un periodo di esecuzione nel caso peggiore di K^2. Quindi alle foglie abbiamo così tanto lavoro in totale:

(N / K) * I(K)
= (N / K) * K * K
= N * K

Ma abbiamo anche un sacco di fusioni da fare, al costo di N per livello dell'albero come spiegato in precedenza. Tornando al nostro metodo precedente, troviamo L (Il numero di livelli prima di raggiungere i sottoproblemi di dimensioni K e quindi passa all'inserimento):

N / 2^L = K
N / K = 2^L
L = log (N/K)

Quindi in totale abbiamo

O(N) = N * K + N * log (N/K)

È passato troppo tempo da quando ho preso algoritmi per darti uno schizzo di prova, ma questo dovrebbe far sparare i tuoi neuroni.