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

Złożoność algorytmu

Object Storage Arubacloud
0 głosów
460 wizyt
pytanie zadane 3 grudnia 2018 w Algorytmy przez VinVix Nowicjusz (240 p.)
Mam za zadanie udowodnić, że f(n)= n(n+1)/2 jest O(n^2).
Czy zapisanie: f(x)=n(n+1) => f(x)=n*(n) => f(x) = n^2 => O(n^2), jest poprawne i wystarczy?

1 odpowiedź

0 głosów
odpowiedź 3 grudnia 2018 przez RafalS VIP (122,820 p.)
edycja 3 grudnia 2018 przez RafalS

Niestety wydaje mi się, że przykład jest zbyt prosty, żeby można było po prostu powiedzieć, że to oczywiste, bo to właśnie zrobiłeś :P.

Powołałbym się zatem na definicje O(), gdzie jest napisane pieknym językiem matematycznym, ze f(n) jest O(g(n)) jesli od pewnego n0 f(n) <= c*g(n) dla dowolnego c >0

Nasze równanie wyglada zatem tak:

n(n+2)/2=0.5n^2 + n = O(n^2) + O(n^2) //nawet O(n) ale na potrzeby obliczen przyjmiemy nawet n^2

https://pl.wikipedia.org/wiki/Asymptotyczne_tempo_wzrostu#Uwagi :

Suma funkcji f1 i f2 O(g(n)) tez jest O(g(n)) jeśli f1*f2 jest O(g^2(n)):

n^4 <= n^4

Podobne pytania

0 głosów
1 odpowiedź 943 wizyt
0 głosów
5 odpowiedzi 2,376 wizyt
pytanie zadane 20 października 2015 w Algorytmy przez starzec Początkujący (410 p.)

92,674 zapytań

141,576 odpowiedzi

320,045 komentarzy

62,038 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!

...