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

Algorytmy - udowodnij z definicji

Fiszki IT
Fiszki IT
0 głosów
69 wizyt
pytanie zadane 24 stycznia w Matematyka, fizyka, logika przez Kajka Nowicjusz (120 p.)
edycja 24 stycznia przez Kajka

Cześć! Mam do rozwiązania zadanie z algorytmów, znam definicje notacji dużego O, ale kompletnie nie wiem jak się za to zabrać, nie wiem czy ominęłam to na wykładach, czy o co chodzi... ale jeśli ktoś mógłby mi to wytłumaczyć, tylko tak jak dla KOMPLETNIE zielonej, będę bardzo wdzięczna!!smiley

Zakładając, że: dla funkcji złożoności obliczeniowej f1(n) istnieje funkcja g1(n) i stała c1 spełniające warunki oszacowania w notacji dużego O ( od góry)

oraz

że: dla funkcji złożoności obliczeniowej f2(n) istnieje funkcja g2(n) i stała c2 spełniające warunki oszacowania w notacji dużego O ( od góry).

Udowodnić następującą własność: Dla funkcji F(n) = f1(n) * f2(n) oszacowanie od góry wynosi: O( g1(n)*g2(n))

~Kajkaa


 

 

1 odpowiedź

0 głosów
odpowiedź 19 kwietnia przez J0ker Stary wyjadacz (11,790 p.)
Dla dostatecznie dużych n (czyli większych od jakiegoś n1), f1(n) <= c1 * g1(n)

Dla dostatecznie dużych n (czyli większych od jakiegoś n2) f2(n) <= c2 * g2(n)

Czyli dla dostatecznie dużych n (większych od maksimum z dwóch liczb (n1, n2)) zachodzi f1(n) * f2(n) <= (c1 * g1(n) )* (c2 * g2(n)) = c1*c2*(g1(n)*g2(n)) = C * (g1(n)*g2(n) gdzie C to c1*c2

Czyli f1*f2 jest O(g1 * g2)

Podobne pytania

0 głosów
1 odpowiedź 285 wizyt
0 głosów
1 odpowiedź 102 wizyt
pytanie zadane 9 grudnia 2019 w Matematyka, fizyka, logika przez KosaTV Obywatel (1,260 p.)
0 głosów
1 odpowiedź 664 wizyt
Porady nie od parady
Zadając pytanie postaraj się o odpowiedni tytuł, kategorię oraz tagi.Tagi

84,702 zapytań

133,503 odpowiedzi

295,887 komentarzy

55,979 pasjonatów

Motyw:

Akcja Pajacyk

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

Oto dwie polecane książki warte uwagi. Pełną listę znajdziesz tutaj.

...