--> Archiwum Forum
QrKo_ [ ]
Złożonośc algorytmów - pytanie.
Sprawa wyglada tak - mam takie zadanko:
Dla danego algorytmu policzyc ilosc wykonywanych operacji i oszacowac
złozonosc w sensie notacji O(·): ->>>>
1. I nastepuje tutaj rozbieznosc opini, jak dla mnie ilosc wykonywanych operacji wynosi n^2, bo obie petle wykonaja sie n razy, po wymnozeniu to daje n^2. Niektorzy jednak twierdza co innego, a notatki jeszcze co innego.
2. Dla porownania lekko inny algorytm - jedyna roznica zostala wyboldowana:
i=0;
dopóki i<n wykonuj:
j=0;
powtarzaj co nastepuje:
j=j+1;
dopóki (j>n);
i=i+1;
I w notatkach z cwiczen mam zapisane ze wykona sie 2n+1 razy, co dla mnie jest dziwne bo n+1 razy wewnetrznej i n razy zewnetrznej chyba powinno byc wymnozone, a nie dodane?
Jesli ktos moze naswietlic te sprawe to bede wdzieczny.
PS Co to kurde jest to O(.) i jak to sie liczy?
peanut [ kriegsmaschine ]
imo zlozonosc jest o(n^2) (o - theta, takie o z kreseczka).
tak jak piszesz, n razy petla zewnetrzna po i, w ktorej sie wykonuje petla wewnetrzna przy kazdej iteracji, a wiec n*(n+1) dla operacji do j=j+1 while j<n;
Scatterhead [ łapaj dzień ]
jeżeli zewnętrzna pętla zawiera drugą pętle (bo z tego rysynku tylko za pomocą formatowania można to stwierdzić, nie ma klamerek, slow poczatkowych i koncowych do bloków kodu), to zlozonosc na 100% to n^2.
QrKo_ [ ]
Dla mnie tez to by bylo oczywiste gdyby nie to ze plrzyklad numer 2 mam przepisany w notatkach krok po kroku i petla wewnetrzna jest n+1 a zewnetrzna n i nie jest to wymnozone tylko dodane - 2n+1.
Mam wrazenie ze babka ktora prowadzi cwiczenia sama tego nie kuma...
Scatterhead [ łapaj dzień ]
Nawet jeżeli już, to 2n+1 to jest dokladny koszt algorytmu w tym przypadku, w notacji O, będzie on zapisany jako O(n) - koszt liniowy.
QrKo_ [ ]
Im dluzej nad tym mysle, tym mniej to rozumiem... Skad mam wiedziec kiedy bedzie n^2 a kiedy 2n? I skad wziac ten koszt liniowy?
reik [ Pretorianin ]
QrKo_:
algorytm na rysunku: n^2 (kwadratowa).
algorytm opisany w punkcie 2: n (liniowa).
Nie chce mi się dokładnie szacować czasu wykonania algorytmów. Teraz odpowiedź dlaczego:
W pierwszym przypadku dzięki warunkowi (j<n) pętla wewnętrzna wykona się "n" razy.
W drugim przypadku dzięki warunkowi: (j>n) pętla wewnętrzna wykona się dokładnie raz (wyjdzie na pierwszym sprawdzeniu warunku).
Jak chcesz sprawdzić i lepiej zrozumieć to podstaw sobie "n=3" i spróbuj prześledzić bieg algorytmu.
peanut [ kriegsmaschine ]
nie ma czegos takiego jak 2n, jest tylko n, ewentualnie cos moze byc wieksze niz n, _O_(n). n to po prostu zlozonosc liniowa, operacje wiec wykonuja sie n + (skonczona ilosc) razy. wtedy masz zlozonosc algorytmu liniowa o_rder(n).
wez sobie ten swoj algorytm rozpisz na elementerne operacje (najprosciej to chyba bedzie po prostu kazda linijke kodu oznaczyc jaka elementrana operacje), pozniej zapisz ile razy kazda z nich wykonasz w pgoramie - petla po i - n (+1, samo spradzenie warunku while) razy, pozniej wewnetrzna po j, ktora wykonujesz juz n(+1 sprawdzenie while)*n razy. dodaj to. wyjdzie ci, ze masz sume zalezna od n*n, a wiec order(n). gdybys mial jedna petle, wtedy tym samym sposobem dojdziesz do o(n).