Differenza tra Big-O e Little-O Notation

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:

• x² ∈ O (x²)
• x² ∈ O (x² + x)
• x² ∈ O (200 * x²)

Quanto segue è vero per il piccolo-o:

• x² ∈ o (x³)
• x² ∈ o (x!)
• ln (x) ∈ o (x)

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 è:

• in O(n²) , o(n²) e O(n)
• non in O(lg n) , o(lg n) o o(n)

Analogamente, il numero 1 è:

• ≤ 2 , < 2 e ≤ 1
• non ≤ 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. 🙂