Crescita Big-O: quanto costa davvero ogni classe di complessità
I tuoi dati
Due algoritmi a confronto diretto
La costante è tutto quello che la notazione butta via: allocazioni, cache miss, il lavoro dentro ogni passo. Dai a un algoritmo una costante più pesante e guarda dove smette di contare.
Questa pagina non legge il tuo ciclo. Indovinare una complessità dal codice sarebbe una congettura travestita da misura: un ciclo può uscire prima, una sola chiamata dentro può nascondere il costo vero, e la ricorsione quasi mai si legge per quello che fa. La classe la scegli tu; quello che la pagina calcola da lì è esatto.
Risultati
| Dove uno supera l'altro, in elementi | — |
| Operazioni di ciascuno, alla dimensione sopra | — |
Con i numeri da cui questa pagina parte, l'incrocio sta a 439 elementi. Chi passa alla classe migliore su una lista di duecento ha reso il programma più lento e il codice più difficile, e la notazione non ha avvertito, perché la notazione parla di quello che succede alla lunga, non di quello che succede a te.
Ogni classe a questa dimensione
| Classe | Operazioni | Tempo | Moltiplicato per, se l'input raddoppia |
|---|
L'ultima colonna è quella da fissare, perché è la colonna che nessuno porta in testa. Il lavoro lineare raddoppia. Quello quadratico quadruplica. Quello esponenziale viene elevato al quadrato: con mille elementi già in gioco, raddoppiare l'input moltiplica il costo per due alla millesima, un numero di trecentodue cifre.
Il fattoriale è peggiore in un modo che non c'entra col raddoppio. Aggiungere un solo elemento moltiplica il costo per il nuovo conteggio, quindi il ventunesimo elemento costa ventuno volte l'intero problema da venti. Ecco perché un commesso viaggiatore esatto su venti città sono 2,4 milioni di milioni di milioni di passi, cioè settantasette anni a un miliardo al secondo, mentre le stesse venti città sotto due alla n finiscono in un millesimo di secondo.
Spiega anche perché il divario tra classi è noioso alle piccole dimensioni e brutale alle grandi. A dieci elementi, n log n e n al quadrato distano tre volte, cosa che nessun utente noterebbe. A mille elementi distano cento volte, e a un milione cinquantamila volte. Gli stessi due algoritmi, lo stesso codice, non è cambiato nulla se non l'input.
Quindi la lettura onesta di una classe di complessità è una promessa sulla forma della curva, non sulla velocità. Dice come reagisce il costo quando l'input cresce, e non dice assolutamente nulla su quanto sia veloce oggi, sulla tua macchina, alla dimensione che hai davvero.
Una classe di complessità migliore vuol dire un programma più veloce?
Alla tua dimensione, non necessariamente. La classe descrive come reagisce il costo quando l'input cresce; non dice nulla del lavoro dentro ogni passo, ed è proprio quel lavoro che la notazione butta via.
Con i numeri da cui questa pagina parte, l'algoritmo quadratico con costante leggera batte quello n log n con costante cinquanta per ogni input sotto i 439 elementi. Sopra, la classe migliore scappa via e non restituisce più il comando.
Perché questa pagina non legge il mio codice?
Perché indovinare la complessità dal sorgente è una congettura travestita da misura. Un ciclo può uscire prima, una chiamata dentro può nascondere il costo vero, e la ricorsione quasi mai si legge per quello che fa.
Quindi qui la classe è un tuo input, non un'opinione della pagina. Tutto ciò che se ne calcola è aritmetica esatta, e niente in questa pagina finge di sapere cosa fa il tuo ciclo.
Cosa succede davvero quando l'input raddoppia?
Il lavoro lineare raddoppia e quello quadratico quadruplica, e quasi tutti lo tengono a mente. Quello esponenziale viene elevato al quadrato, e questo quasi nessuno: a mille elementi, raddoppiare l'input moltiplica il costo per due alla millesima.
Il fattoriale non funziona nemmeno così. Aggiungere un solo elemento moltiplica il costo per il nuovo conteggio, quindi il ventunesimo elemento costa ventuno volte l'intero problema da venti.
| Classe | Moltiplicato per quando l'input raddoppia, a mille elementi |
|---|---|
| O(n) | 2 |
| O(n log n) | 2,2 |
| O(n²) | 4 |
| O(n³) | 8 |
| O(2ⁿ) | 1,07 x 10^301 |
Perché un commesso viaggiatore esatto è impossibile con venti città?
Perché venti fattoriale sono 2,4 milioni di milioni di milioni di passi, che a un miliardo di operazioni al secondo fanno settantasette anni. Gli stessi venti elementi sotto due alla n richiedono circa un millesimo di secondo.
Questa è la differenza pratica tra esponenziale e fattoriale, ed è il motivo per cui vale la pena distinguerli invece di archiviarli entrambi come impossibili.
Reazioni
0
0 Commenti
Diventa il primo a commentare