Mi è stata fatta la seguente domanda ..
Un algoritmo considera n elementi, ordina il 5% di n out, considera gli elementi restanti (95%), ordina il 5% degli elementi rimanenti e così via fino a quando non rimane un ultimo elemento. Che complessità ha l'algoritmo e perché?
La complessità del tempo O grande di algoritmi di divisione e conquista non è influenzata dalla frazione in cui dividi le cose. Questo perché i registri di diverse basi differiscono solo di un fattore costante. Quindi la complessità del tempo di Big O nel tuo caso è la stessa di se si separa il 50%.
Quindi dovresti ottenere il solito ordinamento nLogn.
Leggi altre domande sui tag algorithms complexity sorting