Sono relativamente nuovo all'analisi dell'algoritmo e sto seguendo un corso correlato sulla coursera dove sono venuto a capo di k way merge sort.
La complessità temporale di un ordinamento di unione a 2 vie è n log2 n , di un ordinamento di unione a 3 vie è n log3 n e di un ordinamento di unione a 4 vie è n log4 n .
Ma, nel caso di k-way, la complessità è nk ^ 2. Questo perché prestiamo attenzione alla fusione di parte dell'algo; %codice%.
Ma, nel caso di algoritmi a 2, 3 e 4 vie, prestiamo attenzione alla chiamata ricorsiva di una funzione; (2n + 3n + 4n...kn) .
Qualcuno può spiegare perché è così? O correggere il mio approccio a questa domanda.