Vantaggio dell'ordinamento unione a 2 vie contro n-way

Question

Vantaggio dell'ordinamento unione a 2 vie contro n-way

#1 da (3 voti)

1

È noto che l'ordinamento Merge a 2 vie richiede l'ora N * logN.

Mi chiedo, quale sarebbe il tempo di esecuzione se dividiamo un array della dimensione N in subarray N e poi facciamo la stessa cosa che faremmo per l'unione a 2 vie?

merging sorting

posta Alan Coromano 10.07.2013 - 12:59

fonte

1 risposta

Leggi altre domande sui tag merging sorting

Qual è l'approccio migliore per gestire il codice javascript / ajax in un progetto? Strumento di monitoraggio delle prestazioni e delle prestazioni di canvas HTML5 per Javascript

score 3 · Answer 1

Bene, la ricorrenza sarà:

dovef(n)èlafunzionediunione.

Naturalmentenell'ordinamentounionebidirezionalepossiamofarlointempolineare,quindif(n)=O(n)perilcasok=2.Ingenerale,tuttavia,ilmomentomigliorepossibileèO(nlogk),utilizzando Code prioritarie .

Ora, secondo il Teorema principale puoi risolvere questa ricorrenza e vedere che T(n)=O(n log n).

Quindi nella notazione asintotica sembra che sia il k-way sia l'ordinamento di fusione originale siano uguali. tuttavia, in pratica, l'implementazione dell'originale merge-sort è più semplice e potrebbe richiedere meno sforzo per l'implementazione e la manutenzione.