Co dokładnie reprezentuje notacja duża Ө?

Jestem naprawdę zdezorientowany różnicami między dużą notacją O, dużą Omegą i dużą notacją Theta.

Rozumiem, że duże O to górna granica, a duża Omega to dolna granica, ale co dokładnie oznacza duże Ө (theta)?

Czytałem, że oznacza to ciasne związanie , ale co to znaczy?

Oznacza to, że w danej funkcji algorytm jest zarówno duży-O, jak i duży-Omega.

Na przykład, jeśli tak jest Ө(n), to istnieje pewna stała k, taka, że ​​twoja funkcja (czas wykonania, cokolwiek) jest większa niż n*kdla wystarczająco dużej ni jakaś inna stała, Ktaka że twoja funkcja jest mniejsza niż n*Kdla wystarczająco dużej n.

Innymi słowy, dla wystarczająco dużej wielkości n, jest on umieszczony pomiędzy dwiema funkcjami liniowymi:

Dla k < Ki nwystarczająco duże,n*k < f(n) < n*K

Najpierw zrozumiemy, czym są duże O, duże Theta i duże Omega. Wszystkie są zbiorami funkcji.

Duże O daje górną asymptotyczną granicę , podczas gdy duża Omega daje dolną granicę. Big Theta daje jedno i drugie.

Wszystko, co jest, Ө(f(n))jest także O(f(n)), ale nie na odwrót.
T(n)mówi się, że jest w Ө(f(n))środku, jeśli jest zarówno wewnątrz, jak O(f(n))i wewnątrz Omega(f(n)).
W zestawach terminologii Ө(f(n))jest przecięcie z O(f(n))aOmega(f(n))

Na przykład, w przypadku scalania sortowania najgorszym przypadkiem jest zarówno O(n*log(n))i Omega(n*log(n))- i tak też jest Ө(n*log(n)), ale jest też O(n^2), ponieważ n^2jest asymptotycznie „większe” od niego. Jednak tak nie jest Ө(n^2), ponieważ algorytm nie jest Omega(n^2).

Nieco głębsze wyjaśnienie matematyczne

O(n)jest asymptotyczną górną granicą. Jeśli T(n)tak O(f(n)), to znaczy, że od pewnego n0istnieje stała Ctaka, że T(n) <= C * f(n). Z drugiej strony, big-Omega mówi, że nie jest stała C2, tak żeT(n) >= C2 * f(n)) ).

Nie myl!

Nie mylić z analizą przypadków najgorszych, najlepszych i średnich: wszystkie trzy notacje (Omega, O, Theta) nie są związane z analizą najlepszych, najgorszych i średnich przypadków algorytmów. Każdy z nich można zastosować do każdej analizy.

Zwykle używamy go do analizy złożoności algorytmów (jak powyższy przykład sortowania przez scalanie). Kiedy mówimy „Algorytm A jest O(f(n))”, tak naprawdę mamy na myśli to, że „Złożoność algorytmów w analizie najgorszego ¹ przypadku jest O(f(n))” - co oznacza - skaluje „podobny” (lub formalnie nie gorszy niż) funkcję f(n).

Dlaczego zależy nam na asymptotycznej granicy algorytmu?

Cóż, jest wiele powodów, ale uważam, że najważniejsze z nich to:

1. Znacznie trudniej jest określić dokładną funkcję złożoności, dlatego „idziemy na kompromis” w notacjach duże-O / duże-Theta, które są wystarczająco pouczające teoretycznie.
2. Dokładna liczba operacji zależy również od platformy . Na przykład, jeśli mamy wektor (listę) 16 liczb. Ile operacji to zajmie? Odpowiedź brzmi: to zależy. Niektóre procesory pozwalają na dodawanie wektorów, podczas gdy inne nie, więc odpowiedź różni się w zależności od różnych implementacji i różnych maszyn, co jest niepożądaną właściwością. Jednak notacja duże-O jest znacznie bardziej stała między maszynami i implementacjami.

Aby zademonstrować ten problem, spójrz na poniższe wykresy:

Oczywiste jest, że f(n) = 2*njest „gorszy” niż f(n) = n. Ale różnica nie jest tak drastyczna, jak w przypadku innej funkcji. Widzimy, że f(n)=lognszybko staje się znacznie niższy niż inne funkcje i f(n) = n^2szybko staje się znacznie wyższy niż inne.
Tak więc - z powyższych powodów „ignorujemy” współczynniki stałe (2 * w przykładzie wykresów) i przyjmujemy tylko notację duże-O.

W powyższym przykładzie, f(n)=n, f(n)=2*nbędzie zarówno w, jak O(n)i w Omega(n)- a zatem również będzie w Theta(n).
Z drugiej strony - f(n)=lognbędzie w O(n)(jest "lepszy" niż f(n)=n), ale NIE będzie w Omega(n)- a więc też NIE będzie Theta(n).
Symetrycznie f(n)=n^2będzie w Omega(n), ale NIE O(n), a zatem - też NIE Theta(n).

¹ Zwykle, choć nie zawsze. kiedy brakuje klasy analizy (najgorsza, średnia i najlepsza), tak naprawdę mamy na myśli najgorszy przypadek.

Theta (n): funkcja f(n)należy do Theta(g(n)), jeśli istnieją dodatnie stałe c1i c2takie, które f(n)można umieścić pomiędzy c1(g(n))i c2(g(n)). tzn. podaje zarówno górną, jak i dolną granicę.

Theta (g (n)) = {f (n): istnieją dodatnie stałe c1, c2 i n1 takie, że 0 <= c1 (g (n)) <= f (n) <= c2 (g (n)) dla wszystkich n> = n1}

kiedy mówimy f(n)=c2(g(n))lub f(n)=c1(g(n))reprezentuje asymptotycznie ścisłe związanie.

O (n): Daje tylko górną granicę (może być napięta lub nie)

O (g (n)) = {f (n): istnieją dodatnie stałe c i n1 takie, że 0 <= f (n) <= cg (n) dla wszystkich n> = n1}

ex : Związany 2*(n^2) = O(n^2)jest asymptotycznie mocno, podczas gdy granica 2*n = O(n^2)nie jest asymptotycznie napięty.

o (n): Daje tylko górną granicę (nigdy ścisłą granicę)

zauważalna różnica między O (n) a o (n) to f (n) jest mniejsza niż cg (n) dla wszystkich n> = n1, ale nie jest równa O (n).

np . : 2*n = o(n^2), ale2*(n^2) != o(n^2)

Mam nadzieję, że właśnie tego możesz chcieć znaleźć w klasycznym CLRS (strona 66):

Notacja Big Theta:

Nie ma nic do zepsucia, kolego !!

Jeśli mamy funkcje o wartościach dodatnich f (n) i g (n) przyjmuje argument o wartości dodatniej n, to ϴ (g (n)) zdefiniowane jako {f (n): istnieją stałe c1, c2 i n1 dla wszystkich n> = n1}

gdzie c1 g (n) <= f (n) <= c2 g (n)

Weźmy przykład:

niech f (n) =

g (n) =

c1 = 5 i c2 = 8 i n1 = 1

Spośród wszystkich notacji, notacja ϴ daje najlepszą intuicję dotyczącą tempa wzrostu funkcji, ponieważ daje nam ścisłą granicę, w przeciwieństwie do dużego-o i dużego -omega, które wyznaczają odpowiednio górną i dolną granicę.

ϴ mówi nam, że g (n) jest tak blisko jak f (n), a tempo wzrostu g (n) jest jak najbardziej zbliżone do tempa wzrostu f (n).

Przede wszystkim teoria

1. Duże O = Górna granica O (n)

2. Theta = funkcja porządku - theta (n)

3. Omega = notacja Q (dolna granica) Q (n)

Dlaczego ludzie są tacy zdezorientowani?

W wielu blogach i książkach Podobny jest sposób podkreślenia tego stwierdzenia

„To jest duże O (n ^ 3)” itd.

a ludzie często Mylą się jak pogoda

O (n) == theta (n) == Q (n)

Ale warto pamiętać, że są one po prostu funkcją matematyczną z nazwami O, Theta i Omega

więc mają ten sam ogólny wzór wielomianu,

Pozwolić,

f (n) = 2n4 + 100n2 + 10n + 50 to

g (n) = n4, więc g (n) jest funkcją, która przyjmuje funkcję jako dane wejściowe i zwraca zmienną z największą potęgą,

Takie same f (n) i g (n) dla Poniżej wszystkich wyjaśnień

Big O - Funkcja (zapewnia górną granicę)

Duże O (n4) = 3n4, ponieważ 3n4> 2n4

3n4 jest wartością Big O (n4) Tak jak f (x) = 3x

n4 odgrywa tutaj rolę x , więc

Zastąpienie n4 przez x'so, Big O (x ') = 2x', Teraz oboje jesteśmy szczęśliwi

Więc 0 ≤ f (n) ≤ O (x ')

O (x ') = cg (n) = 3n4

Wartość,

0 ≤ 2n4 + 100n2 + 10n + 50 ≤ 3n4

3n4 to nasza górna granica

Theta (n) zapewnia niższe ograniczenie

Theta (n4) = cg (n) = 2n4 Ponieważ 2n4 ≤ Nasz przykład f (n)

2n4 to wartość Theta (n4)

więc 0 ≤ cg (n) ≤ f (n)

0 ≤ 2n4 ≤ 2n4 + 100n2 + 10n + 50

2n4 to nasza Dolna granica

Omega n - funkcja porządkowa

Jest to obliczane, aby dowiedzieć się, że dolna granica pogody jest podobna do górnej granicy,

Przypadek 1). Górna granica jest podobna do dolnej granicy

if Upper Bound is Similar to Lower Bound, The Average Case is Similar

Example, 2n4 ≤ f(x) ≤ 2n4,
Then Omega(n) = 2n4

Przypadek 2). jeśli Górna granica nie jest podobna do dolnej granicy

in this case, Omega(n) is Not fixed but Omega(n) is the set of functions with the same order of growth as g(n).

Example 2n4 ≤ f(x) ≤ 3n4, This is Our Default Case,
Then, Omega(n) = c'n4, is a set of functions with 2 ≤ c' ≤ 3

Mam nadzieję, że to wyjaśnione !!