Differenza tra Big-O e Little-O Notation

Question

Qual è la differenza tra Big O- O(n) notazione e Little-O notazione o(n)?

Answer 1

f ∈ O (g) dice, in sostanza,

  

almeno un scelta di una costante k > 0, è possibile trovare un costante a in modo tale che la disuguaglianza 0 <= f (x) <= kg (x) vale per ogni x> a.

Si noti che O (g) è l'insieme di tutte le funzioni per cui questa condizione detiene.

f ∈ O (g) dice, in sostanza,

  

ogni scelta di una costante k > 0, è possibile trovare una costante a in modo tale che la disuguaglianza 0 <= f (x ) a.

Ancora una volta, si noti che o (g) è un insieme.

In Big-O, è necessario soltanto che si trova un particolare moltiplicatore di k per il quale la disuguaglianza di là di qualche minima x .

In poco-o, deve essere che ci sia un minimo di x , dopo che la disuguaglianza non tiene importa quanto piccolo a rendere k , fino a quando non lo è negativa o nulla.

Si tratta sia descrivere limiti superiori, anche se un po 'contro-intuitivo, poco-o è la dichiarazione più forte. Esiste un divario molto più grande tra i tassi di crescita di feg se f ∈ O (g) che se f ∈ O (g).

Un esempio della disparità è questa: f ∈ O (f) è vero, ma f ∈ O (f) è falsa. 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ù lento di G". E 'come <= contro <.

In particolare, se il valore di g (x) è un multiplo costante del valore di f (x), allora f ∈ O (g) è vero. Questo è il motivo per cui si può cadere quando si lavora con le costanti notazione O-grande.

Tuttavia, per f ∈ O (g) per essere vero, allora g deve includere un maggiore potenza di x nella formula, e quindi la relativa separazione tra f (x) e g (x ) deve effettivamente ottenere più grande come x diventa più grande.

Per utilizzare puramente esempi matematica (piuttosto che riferirsi ad algoritmi):

Di seguito sono vere per Big-O, ma non sarebbe vero se si è utilizzato poco-o:

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

Di seguito sono vere per i poco-o:

• x² ∈ O (X³)
• x² ∈ O (x!)
• ln (x) ∈ O (x)

Si noti che se f ∈ O (g), questo implica f ∈ O (g). per esempio. x² ∈ o (x³) quindi è anche vero che x² ∈ O (x³), (di nuovo, pensare di O come <= e o come <)

Answer 2

Big-O è quello di poco-o come ≤ è quello di <. Big-O è un inclusiva limite superiore, mentre poco-o è un rigoroso limite superiore.

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: il tavolo è una buona guida, ma la sua definizione limite dovrebbe essere in termini di superiore < . / a> al posto del normale limite, ad esempio, 3 + (n mod 2) oscilla tra il 3 e il 4 per sempre 'in O(1) pur non avendo un limite normale, perché ha ancora un lim sup:.. 4)

Vi consiglio memorizzare come la notazione O-grande si trasforma in confronto asintotici. I confronti sono più facili da ricordare, ma meno flessibile perché non si può dire le cose come n ^{O (1)} = P.

Answer 3

Trovo che quando non riesco a cogliere qualcosa concettualmente, pensare a il motivo per cui si potrebbe usare X è utile per capire X. (Per non dire che non hai provato, io sono solo preparando il terreno.)

[cose che conosci] Un modo comune per classificare gli algoritmi è di runtime, e citando la complessità big-Oh di un algoritmo, è possibile ottenere una buona stima di cui uno è "migliore" - a seconda di quale è il " più piccola funzione" nella O! Anche nel mondo reale, O (N) è "migliore" di O (n²), il blocco delle cose stupide come costanti super-massicci e simili. [/ Cose che conosci]

Diciamo che c'è qualche algoritmo che viene eseguito in O (N). Abbastanza buono, eh? Ma diciamo che (voi persona brillante, voi) arriva con un algoritmo che viene eseguito in O ( ^N / _{loglogloglogN} ). SÌÌ! Il suo più veloce! Ma vi sentireste scrittura sciocca che più e più volte quando si sta scrivendo la sua tesi. Così si scrive una volta, e si può dire "In questo lavoro, ho dimostrato che l'algoritmo X, precedentemente calcolabile in tempo O (N), è infatti calcolabile in O (n)".

In questo modo, tutti sanno che l'algoritmo è più veloce --- da quanto non è chiaro, ma sanno il suo più veloce. Teoricamente. :)