Różnica między notacją Big-O i Little-O

Jaka jest różnica między Big-O notacji O(n)i Little-O notacji o(n)?

f ∈ O (g) mówi zasadniczo

Dla co najmniej jednego wyboru stałej k > 0, można znaleźć stałą takie, że nierówność 0 <= f (x) <= kg (x) zachodzi dla wszystkich x> a.

Zauważ, że O (g) jest zbiorem wszystkich funkcji, dla których ten warunek obowiązuje.

f ∈ o (g) mówi zasadniczo

Dla każdego wyboru stałej k > 0, można znaleźć stałą takie, że nierówność 0 <= f (x) <kg (x) zachodzi dla wszystkich x> a.

Jeszcze raz zauważ, że o (g) jest zbiorem.

W Big-O konieczne jest tylko znalezienie konkretnego mnożnika k, dla którego nierówność utrzymuje się powyżej pewnego minimum x .

W Little-o musi być tak, że istnieje minimum x, po którym nierówność się utrzymuje, bez względu na to, jak małe jest k , pod warunkiem, że nie jest ujemne ani zerowe.

Oba opisują górne granice, choć nieco sprzeczne z intuicją, Little-o jest silniejszym stwierdzeniem. Istnieje znacznie większa różnica między szybkościami wzrostu f i g, jeśli f ∈ o (g) niż jeśli f ∈ O (g).

Jedną z ilustrujących tę różnicę jest: f ∈ O (f) jest prawdą, ale f ∈ o (f) jest fałszem. Dlatego Big-O można odczytać jako „f ∈ O (g) oznacza, że ​​asymptotyczny wzrost f nie jest szybszy niż g's”, podczas gdy „f ∈ o (g) oznacza, że ​​asymptotyczny wzrost f jest ściśle wolniejszy niż g's”. To jak <=kontra <.

Mówiąc dokładniej, jeśli wartość g (x) jest stałą wielokrotnością wartości f (x), wówczas f ∈ O (g) jest prawdziwe. Dlatego możesz upuścić stałe podczas pracy z notacją big-O.

Jednak, aby f ∈ o (g) było prawdziwe, to g musi uwzględniać wyższą moc x we wzorze, a zatem względne oddzielenie między f (x) ig (x) musi faktycznie wzrosnąć, gdy x się powiększy.

Aby użyć przykładów czysto matematycznych (zamiast odwoływania się do algorytmów):

Poniższe są prawdziwe dla Big-O, ale nie byłyby prawdziwe, gdybyś użył little-o:

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

Następujące są prawdziwe dla little-o:

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

Zauważ, że jeśli f ∈ o (g), oznacza to f ∈ O (g). np. x² ∈ o (x³), więc prawdą jest również, że x² ∈ O (x³), (ponownie, myśl o O jako <=i o jako <)

Big-O jest za mało-tak jak ≤jest <. Big-O jest włączającą górną granicą, podczas gdy little-o jest ścisłą górną granicą.

Na przykład funkcja f(n) = 3nto:

• w O(n²), o(n²)iO(n)
• nie O(lg n), o(lg n)lubo(n)

Analogicznie liczba 1to:

• ≤ 2, < 2i≤ 1
• nie ≤ 0, < 0lub< 1

Oto tabela przedstawiająca ogólny pomysł:

(Uwaga: tabela jest dobrym przewodnikiem, ale jej definicja limitu powinna być wyrażona w kategoriach górnego limitu zamiast normalnego limitu. Na przykład 3 + (n mod 2) oscyluje między 3 a 4. na zawsze. Jest w nim O(1)pomimo tego, że nie ma normalnego limitu, ponieważ wciąż ma a lim sup: 4.)

Polecam zapamiętanie, w jaki sposób notacja Big-O przekształca się w asymptotyczne porównania. Porównania są łatwiejsze do zapamiętania, ale mniej elastyczne, ponieważ nie można powiedzieć rzeczy takich jak n ^{O (1)} = P.

Uważam, że kiedy nie mogę pojęć koncepcyjnie, myślenie o tym, dlaczego ktoś użyłby X, pomaga zrozumieć X. (Nie mówiąc już, że tego nie próbowałeś, po prostu przygotowuję scenę).

. w O! Nawet w prawdziwym świecie O (N) jest „lepsze” niż O (N²), wykluczając głupie rzeczy, takie jak super-masywne stałe i tym podobne. [/ Rzeczy, które znasz]

Powiedzmy, że jest jakiś algorytm działający w O (N). Całkiem dobrze, co? Ale powiedzmy, że ty (ty błyskotliwa osoba) _wymyślisz algorytm działający w O ( ^N ⁄ _{loglogloglogN} ). TAK! Jest szybsze! Ale czułbyś się głupio, pisząc to w kółko, pisząc swoją tezę. Więc piszesz to raz i możesz powiedzieć: „W tym artykule udowodniłem, że algorytm X, wcześniej obliczalny w czasie O (N), w rzeczywistości jest obliczalny w o (n)”.

Zatem wszyscy wiedzą, że twój algorytm jest szybszy - o ile niejasny, ale wiedzą, że jest szybszy. Teoretycznie :)