Qual è la spiegazione semplice per O(n log n)?

Se qualcosa richiede un tempo proporzionale a log n questo significa che se hai n cose puoi fare qualsiasi cosa tu voglia fare in un tempo proporzionale non al numero n, ma proporzionale al numero di cifre in n. Tipicamente quando si parla di algoritmi si usa la base due piuttosto che la base 10, quindi si intende che il tempo è proporzionale al numero di cifre nella rappresentazione binaria di n. Ma poiché tutti i log sono legati tra loro da una costante la proporzionalità sarebbe valida indipendentemente dalla base.

Ora pensa ad un numero binario. Come faresti a decidere quale sia quel numero in un tempo proporzionale a log n. Dovresti fondamentalmente decidere ad ogni passo quale sia una nuova cifra in quel numero. Ogni volta che si decide se una cifra è 1 o 0 si divide il numero di valori possibili per n in 2.

La maggior parte dei problemi che coinvolgono n cose sono almeno O(n) perché se fosse meno di questo si potrebbe risolvere il problema senza nemmeno guardare tutte le n cose. O(n log n) significa che per ogni cosa devi fare un lavoro extra proporzionale al numero di cifre nel conteggio che descrive cosa stai guardando. Non molto, perché tipicamente il numero di cifre in un numero è molto più piccolo del valore di quel numero, ma comunque un po'. E significa che se n diventa sempre più grande, anche la quantità di lavoro extra diventa più grande per ogni elemento di n.