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

Algorytmy i Struktury danych

VPS Starter Arubacloud
+1 głos
318 wizyt
pytanie zadane 17 listopada 2020 w Matematyka, fizyka, logika przez Kaiya Nowicjusz (130 p.)
edycja 17 listopada 2020 przez Kaiya

Czy można ograniczyć duże O (ograniczenie górne) Omegą (ograniczenie dolne) inną niż Omega(1)? Pytałam się dwóch ćwiczeniowców i jeden mówi ze odpowiedz błędna a drugi że wszystko się zgadza. (Chodzi o pierwsza odpowiedz z Omegą) lepsza jakość - Screen zadania: https://imgur.com/a/ssboyXh
Skoro we wszystkich sytuacjach nasze W posiada górne ograniczenie W(Alg, n) = O (...) to wydawało mi się że jedyne czym możemy ograniczyć duże O z dołu jest Ω(1).

1 odpowiedź

0 głosów
odpowiedź 17 listopada 2020 przez Wiciorny Ekspert (274,410 p.)
edycja 17 listopada 2020 przez Wiciorny
Czym jest Omega (1)? Funkcja liniową - stałą o wartości jeden,  ona nie ogranicza funkcji rosnącej więc ogranicza tylko funkcje które nigdy nie będą większe niż 1.
Niestety nie ma ograniczenia dolnego ponieważ dla wartości ułamkowych funkcja jest 1/limes -> nieskończoności bo bo choćby 1/2 jest już mniejsze niż 1.
natomiast 1/nieskończoność zbliża się do 0. stąd granica dolna to 0
komentarz 17 listopada 2020 przez Kaiya Nowicjusz (130 p.)
Wydaje mi się że algorytm nie może mieć dolnego ograniczenia 0, bo wykona się co najmniej raz więc złożoność (nieważne czy w sytuacji Average czy Worst) nie może wynosić mniej niż 1.
komentarz 17 listopada 2020 przez Wiciorny Ekspert (274,410 p.)
ale nie mówie, że ma ... granica to 0, nie ograniczenie... algorytm nigdy nie osiągnie 0, ale zmierza bo 1/ n -> do nieskończoności ma granice 0

Podobne pytania

+1 głos
1 odpowiedź 1,425 wizyt
–1 głos
2 odpowiedzi 632 wizyt
pytanie zadane 27 lutego 2020 w Rozwój zawodowy, nauka, praca przez kaminie318 Bywalec (2,070 p.)
0 głosów
1 odpowiedź 511 wizyt

92,775 zapytań

141,703 odpowiedzi

320,571 komentarzy

62,110 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

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!

...