Costanti e Big O [duplicato]

1

Le costanti sono sempre irrilevanti anche se sono grandi?

Ad esempio è O (10 ^ 9 * N) == O (N)?

    
posta ConditionRacer 09.04.2013 - 01:35
fonte

2 risposte

7

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.

    
risposta data 09.04.2013 - 01:41
fonte
4

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.

    
risposta data 09.04.2013 - 02:22
fonte

Leggi altre domande sui tag