Le costanti sono sempre irrilevanti anche se sono grandi?
Ad esempio è O (10 ^ 9 * N) == O (N)?
Le costanti sono sempre irrilevanti anche se sono grandi?
Ad esempio è O (10 ^ 9 * N) == O (N)?
Big O descrive come un algoritmo ridimensiona; non, in senso stretto, quanto tempo ci vuole per eseguire.
Nel tuo esempio, se il tempo necessario per eseguire più di 1 elemento è grande, ci vorrà un tempo (non banale) per eseguire l'algoritmo, anche se è applicato a un elemento. Ma quell'algoritmo aumenterà ancora nel tempo linearmente. Quindi se lo colpisci con 100 voci, puoi aspettarti che duri 100 volte di più.
Lo stesso non si può dire di un algoritmo O (n ^ 2); non importa quanto piccola sia la costante lineare, finirà comunque per superare il tempo necessario per eseguire l'algoritmo lineare (aumentando N).
La costante lineare è quindi in definitiva irrilevante.
Dipende da cosa stai usando per te l'analisi.
Se lo stai usando solo per dirti in che modo il tuo algoritmo si ridimensiona nel limite (cioè quando N va all'infinito), le costanti non sono rilevanti.
Se sei preoccupato (e probabilmente dovresti esserlo) con quali saranno probabilmente i numeri effettivi delle prestazioni, allora le costanti sono significative ... e anche i termini di ordine inferiore potrebbero essere significativi.
Big O è un modo di semplificare l'analisi della complessità per rispondere a una domanda correlata al rendimento. Ci sono altre domande che sono ugualmente rilevanti.
Leggi altre domande sui tag big-o