Qualcuno può spiegarmi in modo semplice perché le costanti non hanno importanza quando si parla di notazione O grande? Perché la complessità rimane la stessa quando aggiungi una costante. Questa non è una domanda per i compiti a casa, voglio solo capirlo meglio. Consentitemi di capire bene O è per vedere il comportamento di una funzione mentre si avvicina all'infinito giusto?Complessità. Perché le costanti non contano?
Ho capito. Grazie mille a tutti.
Non importa per la teoria della complessità, che è interessata solo in come la funzione si ridimensiona man mano che la dimensione di input aumenta.
Una costante non influisce sul modo in cui la funzione si comporta come le dimensioni dell'input crescono verso l'infinito.
Tuttavia, se si è interessati a eseguire effettivamente una determinata parte di codice, si potrebbe essere interessati a un grande sovraccarico costante e a come la funzione viene eseguita per le dimensioni di input più piccole.
Differenza tra teoria della complessità e pratica.
Notazione Big-O riguarda il modo in cui l'utilizzo delle risorse (tempo, memoria) cambia quando cambia il numero di elementi. Ad esempio, se il mio computer è in grado di ordinare 10 elementi in 1 secondo, 20 elementi in 4 secondi e 30 elementi in 9 secondi, allora è O (n ²).
Se riesco a ordinare gli stessi oggetti a mano rispettivamente in 10 secondi, 40 secondi e 90 secondi, allora sono ancora O (n ²), ma il mio fattore costante è 10 volte più grande: la stessa dimensione del problema mi prende dieci volte il tempo che il computer.
La risposta è ... per definizione. Se alcune funzioni f(x) sono grandi-O di qualche funzione g(x), significa semplicemente che lo f(x) è "alla fine" più piccolo di alcune volte costanti g(x). (vale a dire per abbastanza grande x). Il valore reale della costante non ha importanza; né la posizione del comportamento "alla fine" - purché sia vero per uno x sufficientemente grande e una costante abbastanza grande, sei coperto.
È possibile aggiungere costanti, o qualsiasi cosa con un O più piccolo, e non importa - è tutto su quale termine cresce il più veloce, e quale termine domina come x cresce.
Big O spiega come la complessità cambia quando l'input diventa grande. Più grande è il tuo input e le costanti meno importanti sono. Ad esempio, moltiplicare qualcosa per 10 è significativamente meno importante della quadratura di qualcosa quando n arriva a un milione o un miliardo. Big O non è una misura esatta, è un modo per mettere il tuo algoritmo in una rozza classe di complessità in modo da poter arrotondare le costanti perché non sono significative con enormi valori n.
In pratica, a volte le costanti fanno questione. Ma, quando parliamo di notazione Big O, stiamo osservando un comportamento asintotico. Il motivo per cui una costante non influisce sul comportamento asintotico è perché una funzione con una curva in crescita più rapida sarà sempre superare una funzione con una curva più lenta anche in presenza di una costante enorme (anche se ci vorrà più tempo per arrivarci, ovviamente).
Quindi diciamo che la costante "non ha importanza", perché non può mai cambiare la relazione asintotica tra le curve.
Le costanti non sono importanti nella notazione O grande perché la preoccupazione è la scalabilità.
a meno che non si desideri ridimensionare ... – Thilo
Poiché la costante è indipendente da N: non cambia, cioè è costante. –