Qual è la differenza tra notazione Big-O O(n)
e notazione Little-O o(n)
?
f ∈ O (g) dice, essenzialmente
Per almeno una scelta di una costante k > 0, puoi trovare una costante a tale che la disuguaglianza 0 <= f (x) <= kg (x) valga per tutti x> a.
Si noti che O (g) è l’insieme di tutte le funzioni per le quali questa condizione è valida.
f ∈ o (g) dice, essenzialmente
Per ogni scelta di una costante k > 0, puoi trovare una costante a tale che la disuguaglianza 0 <= f (x)
a.
Ancora una volta, nota che o (g) è un insieme.
In Big-O, è necessario solo trovare un particolare moltiplicatore k per il quale la disuguaglianza vale oltre un minimo x .
In Little-o, deve essere che ci sia un x minimo dopo il quale la disuguaglianza continua a prescindere da quanto piccolo si fa k , purché non sia negativo o zero.
Entrambi descrivono i limiti superiori, anche se in qualche modo contro-intuitivamente, Little-o è l’affermazione più forte. C’è un divario molto più grande tra i tassi di crescita di f e g se f ∈ o (g) rispetto a f ∈ O (g).
Un’illustrazione della disparità è questa: f ∈ O (f) è vero, ma f ∈ o (f) è falso. Pertanto, Big-O può essere letto come “f ∈ O (g) significa che la crescita asintotica di f non è più veloce di g”, mentre “f ∈ o (g) significa che la crescita asintotica di f è strettamente più lenta di g”. È come <=
contro <
.
Più specificamente, se il valore di g (x) è un multiplo costante del valore di f (x), allora f ∈ O (g) è vero. Questo è il motivo per cui è ansible rilasciare le costanti quando si lavora con la notazione big-O.
Tuttavia, per f ∈ o (g) per essere vero, allora g deve includere una maggiore potenza di x nella sua formula, e quindi la relativa separazione tra f (x) e g (x) deve effettivamente diventare più grande quando x diventa più grande.
Per utilizzare esempi puramente matematici (piuttosto che riferirsi ad algoritmi):
Quanto segue è vero per Big-O, ma non sarebbe vero se tu usassi little-o:
Quanto segue è vero per il piccolo-o:
Notare che se f ∈ o (g), ciò implica f ∈ O (g). per esempio x² ∈ o (x³) quindi è anche vero che x² ∈ O (x³), (ancora, pensa a O come <=
e o come <
)
Big-O è a little-o as ≤
is to <
. Big-O è un limite superiore compreso, mentre little-o è un limite superiore rigoroso.
Ad esempio, la funzione f(n) = 3n
è:
O(n²)
, o(n²)
e O(n)
O(lg n)
, o(lg n)
o o(n)
Analogamente, il numero 1
è:
≤ 2
, < 2
e ≤ 1
≤ 0
, < 0
o < 1
Ecco una tabella, che mostra l'idea generale:
(Nota: la tabella è una buona guida, ma la sua definizione limite dovrebbe essere in termini di limite superiore invece del limite normale.Ad esempio, 3 + (n mod 2)
oscilla tra 3 e 4 per sempre. È in O(1)
nonostante non abbia un limite normale, perché ha ancora un lim sup
: 4.)
Raccomando di memorizzare come la notazione Big-O converte in confronti asintotici. I confronti sono più facili da ricordare, ma meno flessibili perché non si possono dire cose come n O (1) = P.
Trovo che quando non riesco a cogliere concettualmente qualcosa, pensare al motivo per cui si usa X è utile per capire X. (Per non dire che non l’hai provato, sto solo preparando il palco).
[cose che conosci] Un modo comune per classificare gli algoritmi è tramite runtime e, citando la complessità di un algoritmo, è ansible ottenere una stima abbastanza buona di quale sia “migliore”, a seconda di quale sia la funzione “più piccola” nella O! Anche nel mondo reale, O (N) è “migliore” di O (N²), salvo cose stupide come costanti super-massive e simili. [/ Cose che conosci]
Diciamo che c’è un algoritmo che gira in O (N). Abbastanza bene, eh? Ma diciamo che tu (tu geniale, tu) hai un algoritmo che gira in O ( N / loglogloglogN ). SÌÌ! È più veloce! Ma ti sentiresti stupido a scriverlo più e più volte mentre scrivi la tua tesi. Quindi lo scrivi una volta, e puoi dire “In questo articolo, ho dimostrato che l’algoritmo X, precedentemente calcolabile nel tempo O (N), è in effetti computabile in o (n).”
Quindi, tutti sanno che il tuo algoritmo è più veloce — da quanto non è chiaro, ma sanno che è più veloce. Teoricamente. 🙂