Considera an^2 + bn + c . Comprendo che per il grande n , bn e c diventano insignificanti.
Capisco anche che per il grande n , le differenze tra 2n^2 e n^2 sono piuttosto insignificanti rispetto a le differenze tra, diciamo n^2 e n*log(n) .
Tuttavia, esiste ancora un ordine di 2 differenze tra 2n^2 e n^2 . Questo importa in pratica? O le persone pensano solo agli algoritmi senza coefficienti? Perché?
Sì, i fattori costanti contano molto nella pratica. La notazione Big-O è solo il primo passo (anche se molto utile) nel misurare le prestazioni di un algoritmo / programma. Un algoritmo che richiede solo n ^ 2 passaggi è sicuramente preferibile a uno che richiede 2 * n ^ 2 passi, a parità di tutte le altre condizioni.
Alla fine il tempo di esecuzione [secondi] dell'implementazione di un algoritmo è il fattore decisivo, ma i coefficienti e la notazione O grande ti aiutano a inventare algoritmi efficienti.
La notazione O grande indica come si comporta l'algoritmo se il numero di input / .. n cambia drasticamente (ordini di grandezza). Lo usi principalmente in senso relativo, cioè aumenta il polinomio, il lineare, il nlog (n), ...
Se confronti due algoritmi che hanno termini big-O simili dovresti includere i coefficienti. Potrebbe essere che l'algoritmo di ordine peggiore, ma con un coefficiente migliore, sia effettivamente più veloce per i tuoi set di dati tipici e non vuoi perderlo.
E finalmente nella pratica le persone spesso prendono solo alcune implementazioni e le lasciano correre l'una contro l'altra. Offre una visione pratica vicino alla realtà (hardware utilizzato e set di dati tipici) ma dipende dall'implementazione, dall'hardware e dai set di dati utilizzati.
Tutti insieme sono i migliori.
Ciò che conta è soggettivo. Tuttavia, sei corretto sul fatto che i coefficienti non sono del primo ordine di importanza. I coefficienti sono spesso ignorati soprattutto perché non c'è il potenziale per migliorare un algoritmo preoccupandoci di essi.
Di conseguenza, non mi dispiacerebbe modificare il codice per ottenere n^2 in n*log(n) . Ma passare da 2n*log(n) a n*log(2n) non è qualcosa che sarei disposto a rendere più difficile leggere il mio codice.
Leggi altre domande sui tag algorithms algorithm-analysis