Notacja Omega i duże Theta

Question

Hej, nie wiem czy w dobrym dziale to napisałem, ale potrzebuje normalnego wyjaśnienia na dwa zadania:

czym jest notacja Ω, co to znaczy, że g(n)= Ω(f(n)) oraz czym jest notacja θ, co to znaczy, że g(n)= θ(f(n))

Szukam po googlach, żeby mieć to normalnie wyjaśnione, ale na żadnej stronie nie potrafie tego w pełni zrozumieć.

Dziękuję i pozdrawiam,

Answer 1

Zacznijmy może od notacji O(f(n)) ("duże o"). Jeśli f(n) = O(g(n)) to znaczy, że istnieje pewne n0 od którego funkcja f będzie mniejsza od funkcji g z dokładnością do stałej c, można powiedzieć że będzie ograniczana przez funkcje g z góry, matematycznie wygląda to tak: f(n) < c * g(n), n >= n0. Od pewnego n0 funkcja f będzie zawsze mniejsza niż g. Weźmy przykład z wikipedii:

Tutaj akurat jest na x zamiast n, ale skoro zabrnąłeś tak daleko w matematyke to wiesz, że nie ma różnicy :D. Widzimy, że od pewnego x0 tutaj jakoś 4.5 niebieska funkcja jest większa od czerwonej i to się już nie zmieni aż do nieskończoności. Stała może wynosić 5, 0.000000001 albo nawet 999999999, grunt, że jest to skończona liczba większa od 0. Np n = O(n^2), bo od n0 = 1 i c = 1: c * n^2 będzie zawsze większe od n. Stałe możesz sobie wbrać inne, ważne żeby istniała taka jedna para, dla której równanie jest spełnione: np c = 2 i n0=2.
Notacja z omegą działa tak samo ale obraca zależność. Oznacza, że od pewnego n0 funkcja f będzie większa od funkcji g.
Notacja theta oznacza, że funkcja f od pewnego n0 będzie się mieścić w przedziale c1*g(n) i c2*g(n):
 
Np 2x = theta(x), bo funkcja f(x) = x zmieści się pomiędzy funkcją x np dla stałych c1 = 0.5 i c2 = 2.

Jeśli dalej masz problemy to możesz zerknąć na tą stronke:
https://pl.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/asymptotic-notation
Omawia ona te notacje od praktycznej strony, bo wykorzystuje się je bardzo często w opisywaniu złożoności algorytmów.

Answer 2

Masz może się przyda ja to tu ogarniałem:

http://th-www.if.uj.edu.pl/~erichter/dydaktyka/Dydaktyka2017/TPI-2017/TPI-wyklad-3-2017.pdf

z przedmiotu na mojej uczelni 3 lata temu, masz opisane dokładnie z przykładami i wykresem ;] zarówno obie

Comments

Chodzi mi o słowne wytłumaczenie raczej.

Bo widze tam znów te ograniczenia z góry z dołu, ze jeden jest dla pesymistycznego, drugi dla optymistycznego. O ile co znaczy pesymistyczny i optymistyczny przypadek tak tych z ograniczeń z góry, z dołu nie czaje.

---

ewentualnie jeden przykład byś mógł mi napsiać, chociażby ten pierwzy, bo drugi to pewnie analogicznie ogarne.