Unisci ordinamento e O (n log n) mistero

Question

Unisci ordinamento e O (n log n) mistero

#1 da (2 voti)
#2 da (1 voti)

2

Ho letto ogni spiegazione qui ma non ne sono ancora convinto. Penso che il mergesort sia n * n e so che ho torto ma non sono sicuro di dove. Ecco cosa penso:

Supponiamo di ordinare 8 elementi e questo è l'algoritmo (supponendo di avere l'idea giusta per questo):

doSort(int begin, int end, int[] arr) {
    if(end != begin) {
        int mid = begin + (end - begin)/2;
        doSort(begin,mid);
        doSort(mid + 1, end);
        merge(arr, begin, mid, mid + 1, end);
    }  
}
merge(int[] arr,int i_begin, i_end, j_begin, j_end) {
// Do the comparison and all that
}

Ora come ho capito la mia fusione () ha la complessità O (n). Ora vediamo quante volte viene chiamato doSort () e quindi merge (). doSort () viene chiamato per i seguenti indici:

0-7
0-3
4-7
0-1
2-3
4-5
6-7

Che è 7 volte che è O (n) dato che stiamo ordinando 8 elementi. Allo stesso modo per 16 elementi, l'unione () viene chiamata 15 volte e così via. Quindi, sebbene dividiamo l'array in metà ogni volta, non eliminiamo l'altra metà con qualsiasi mezzo. Confronta questo con una ricerca BST in cui elimino metà dell'albero ad ogni passaggio perché so che l'altra metà è inutile per me, che secondo me è vero log (n). E in caso di un tipo di merge, chiamiamo merge n-1 volte e ogni volta che merge ha bisogno di operazioni o (n), quindi O (n * n).

Dove ho sbagliato? Qualsiasi suggerimento sarebbe apprezzato.

array algorithms big-o sorting

posta Mustafa 18.02.2016 - 05:58

fonte

2 risposte

Leggi altre domande sui tag array algorithms big-o sorting

Dovremmo usare l'oggetto dati (o l'oggetto di trasferimento dati) per condividere i dati tra queste tre classi? Unique_ptr per conservare la memoria per la VM personalizzata

score 2 · Answer 1

L'ordinamento dice 1.024 numeri, si esegue una fusione di due array di 512 elementi. Esegui 2 unioni di due matrici di 256 elementi, 4 unioni di due matrici di 128 elementi, 8 tims 64 elementi, ..., 512 unioni di due matrici di 1 elemento.

Hai appena controllato l'ora per la fusione più grande (1 x 512 elementi) e il numero totale di unioni (1.023 unioni), ma non ti sei reso conto che metà delle unioni erano solo 1 array di elementi, metà del resto le unioni erano solo 2 array di elementi e così via. Ogni serie di unioni richiede n = 1024 passi (una unione con risultato elemento 1024, 2 unione con 512 risultati elemento, ..., 512 unione con 2 risultati elemento), e ci sono log2 (n) = 10 insiemi di unioni, per un totale di 10 x 1024 o (n log2 n) passi.

score 1 · Answer 2

La complessità dell'ordinamento di unione è O (nlogn) e NOT O (n * n).

Unisci ordinamento è un algoritmo di divisione e conquista. Pensaci in termini di 3 passaggi -

La divisione divide calcola il punto medio di ciascuno dei sottosegmenti. Ognuno di questi passaggi richiede solo O (1) tempo. Il passo di conquista ordina in modo ricorsivo due subarray di n / 2 (per anche n) elementi. Il passo di unione unisce n elementi che impiegano O (n) tempo.

Ora, per i passi 1 e 3 cioè tra O (1) e O (n), O (n) è più alto. Prendiamo in considerazione i passaggi 1 e 3, che impiegano O (n) in totale. Dì che è cn per qualche costante c.

Quante volte vengono eseguiti questi passaggi?

Per questo, guarda l'albero sottostante - per ogni livello dall'alto al basso il livello 2 chiama il metodo di unione su 2 sotto-array di lunghezza n / 2 ciascuno. La complessità qui è 2 * (cn / 2) = cn Il livello 3 chiama il metodo di unione su 4 sotto-array di lunghezza n / 4 ciascuno. La complessità qui è 4 * (cn / 4) = cn e così via ...

Ora, l'altezza di questo albero è (logn + 1) per un dato n. Quindi la complessità complessiva è (logn + 1) * (cn). Questo è O (nlogn) per l'algoritmo di merge sort.