Jaka jest różnica między Big-O notacji O(n)i Little-O notacji o(n)?
Różnica między notacją Big-O i Little-O
Odpowiedzi:
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 <)
146
Tak - różnica polega na tym, czy dwie funkcje mogą być asymptotycznie takie same. Intuicyjnie lubię myśleć o dużym-O, co oznacza „rośnie nie szybciej niż” (tj. Rośnie w tym samym tempie lub wolniej), a małe-o oznacza „rośnie ściśle wolniej niż”.
—
Phil
Skopiować to na wikipedię? To o wiele lepsze niż to, co tam jest.
—
cloudsurfin
@SA Tak. To trudniejszy przypadek, w którym prostsza reguła, którą podałem o „wyższych mocach x”, oczywiście nie ma zastosowania. Ale jeśli spojrzysz na bardziej rygorystyczne definicje limitów podane w odpowiedzi Strilanc poniżej, to chcesz wiedzieć, czy lim n-> inf (2 ^ n / 3 ^ n) = 0. Od (2 ^ n / 3 ^ n) = (2/3) ^ n, a ponieważ dla dowolnego 0 <= x <1, lim n-> inf (x ^ n) = 0, prawdą jest, że 2 ^ n = o (3 ^ n).
—
Tyler McHenry
Uważaj na „W Little-o musi być 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”. To nie jest „dla każdego
—
GA1
ajest k, że: ...”, to jest „dla każdego kistnieje a, że: ...”
„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.” nie, to jest niepoprawne.
—
Filippo Costa
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.
Mam jedno pytanie: jaka jest różnica między linią 3 i 4 (kolumna definicji limitów)? Czy możesz mi pokazać jeden przykład, w którym 4 zawiera (lim> 0), ale nie 3?
—
Masked Man
Och, rozgryzłem to. Big Omega jest dla lim> 0, Big Oh jest dla lim <nieskończoności, Big Theta jest wtedy, gdy oba warunki się utrzymują, co oznacza 0 <lim <nieskończoność.
—
Masked Man
Czy dla f ∈ Ω (g) granica nieskończoności nie powinna wynosić>> 1? Podobnie dla f ∈ O (g), 1 = <c <∞?
—
user2963623,
@ user2963623 Nie, ponieważ wartości skończone ściśle powyżej 0, w tym wartości od 0 do 1, odpowiadają „tej samej asymptotycznej złożoności, ale innym stałym czynnikom”. Pominięcie wartości poniżej 1 spowoduje odcięcie w przestrzeni o stałym współczynniku zamiast w przestrzeni o złożoności asymptotycznej.
—
Craig Gidney
@ubadub Transmitujesz operację potęgowania przez zestaw. To luźna notacja.
—
Craig Gidney
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 :)