• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Notacja Omega i duże Theta

VPS Starter Arubacloud
+1 głos
3,827 wizyt
pytanie zadane 12 maja 2018 w Matematyka, fizyka, logika przez must Bywalec (2,980 p.)
edycja 13 maja 2018 przez must
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,

2 odpowiedzi

+2 głosów
odpowiedź 13 maja 2018 przez RafalS VIP (122,820 p.)
wybrane 13 maja 2018 przez must
 
Najlepsza

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.

+1 głos
odpowiedź 13 maja 2018 przez Wiciorny Ekspert (269,120 p.)
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
komentarz 13 maja 2018 przez must Bywalec (2,980 p.)
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.
komentarz 13 maja 2018 przez must Bywalec (2,980 p.)
ewentualnie jeden przykład byś mógł mi napsiać, chociażby ten pierwzy, bo drugi to pewnie analogicznie ogarne.

Podobne pytania

0 głosów
1 odpowiedź 736 wizyt
pytanie zadane 23 listopada 2020 w Systemy operacyjne, programy przez T100 Obywatel (1,450 p.)
0 głosów
1 odpowiedź 343 wizyt
pytanie zadane 7 czerwca 2020 w Matematyka, fizyka, logika przez Eryk Skoczylas Nowicjusz (120 p.)
0 głosów
1 odpowiedź 451 wizyt
pytanie zadane 11 marca 2019 w Algorytmy przez adam11 Użytkownik (570 p.)

92,451 zapytań

141,261 odpowiedzi

319,073 komentarzy

61,853 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...