È O (log n) + O (log n) = O (n)? [duplicare]

No, O(log n) + O(log n) non è O(n) . È ancora O(log n) . Quando abbiamo una formula O grande moltiplicata per una costante, equivale al valore senza la costante moltiplicata . Quindi:

O(k * g) = O(g)

dove k è un fattore costante, diverso da zero e g è una funzione di delimitazione.

Un'operazione O(log n) è un'operazione che richiede un numero di passi proporzionale al logaritmo (spesso base-2, ma non sempre e non è necessario che sia) della dimensione dell'input, denotata da n . Quando hai più operazioni dello stesso ordine big-O, puoi aggiungerle come hai fatto, e uscire con qualcosa come O(2 * log n) , ma la notazione O grande non riguarda i fattori moltiplicativi costanti, quindi ignoriamo il 2 e scrivi O(log n) .

Il motivo per cui non ci occupiamo di fattori costanti ^* è che stiamo esaminando il potenziale di crescita di un algoritmo in base alla dimensione dell'input. Non lo usiamo per calcolare il numero esatto di passaggi, solo per vedere come potrebbe aumentare il numero di passaggi.

Diamo un'occhiata ad alcuni numeri reali per darci un esempio matematicamente meno astratto. Abbiamo un algoritmo eseguito in O(log n) time e richiede esattamente log ₂ (n) passi. Abbiamo un metodo in cui viene eseguito una volta con un input della dimensione 8. Sono necessari 3 passaggi. Abbiamo un altro metodo in cui viene eseguito due volte, quindi sono necessari 6 passaggi. Questo non è il paragone che ci interessa, però. Vogliamo sapere della crescita . Eseguiamo di nuovo il primo metodo con una dimensione di input di 16. Sono necessari 4 passaggi per completare, + 33% di passaggi in più. Eseguiamo il secondo metodo con una dimensione di input di 16. Sono necessari 8 passaggi per completare, anche + 33% di passaggi in più . Possiamo vedere che, sebbene il numero di passaggi sia diverso, la crescita è la stessa tra le funzioni. Il tasso di crescita è O(log n) nonostante il numero di volte in cui è chiamato, ed è il tasso di crescita a cui siamo interessati.

^* Non ci interessano anche le parti con funzioni di delimitazione della crescita inferiore, quindi O(n + log n) equivale a O(n) .

Sia O (log n) che O (2 log n) sono sottoinsiemi di O (n). Sono entrambi uguali a O (log n).

Devi ricordare che O (log n) è un set , è (informalmente) "l'insieme di tutte le funzioni che non crescono significativamente più velocemente di f (x) = log x" . Quindi, tutte le seguenti sono vere

• O (log n) = O (2 log n)
• O (log n) ⊂ O (n)
• O (2 log n) ⊂ O (n)
• ∀f: f ∈ O (2 log n) ⇒ f ∈ O (n)

Puoi facilmente verificarlo collegando le funzioni alla definizione di O (g).

Sfortunatamente, c'è un sacco di abusi sulla notazione in corso a questo riguardo. Ad esempio, f ∈ O (g) è spesso scritto f = O (g), anche se non ha senso: f è una funzione, O (g) è un insieme di funzioni. Una mela non può mai essere uguale a un set di mele! Allo stesso modo, spesso è scritto che O (f) = O (g), quando ciò che si intende veramente è O (f) ⊂ O (g). Infine, la gente a volte afferma che f (n) = 2n è un elemento di O (n) ma non di O (n²), che è sbagliato. O (n) è un sottoinsieme di O (n²), quindi qualsiasi funzione che si trova in O (n) è anch'essa in O (n²).

Per valori grandi di n, le costanti vengono ignorate nella notazione Big O.

Quindi

O (log n) + O (log n) = O (2log n) - > O (log n)