[Algorytmy] Sposoby na obliczanie złożoności algorytmu

PAV38
Użytkownik
Użytkownik
Posty: 149
Rejestracja: 24 paź 2010, o 09:50
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 18 razy
Pomógł: 2 razy

[Algorytmy] Sposoby na obliczanie złożoności algorytmu

Post autor: PAV38 » 13 mar 2012, o 22:11

No właśnie, chciałbym dowiedzieć, czy istnieją jakieś uniwersalne metody dotyczące obliczania złożoności algorytmów? Dokładniej, rzecz biorąc chodzi mi o zadania, w których mamy napisany pseudo-kod jakiegoś programu i na jego podstawie mamy określić jego złożoność obliczeniową. Czy są jakieś uniwersalne sztuczki, pozwalające na szybkie rozwiązywanie tego typu problemów? Czy w takim pseudo-kodzie można wyróżnić jakieś charakterystyczne elementy, które z góry dają nam odpowiedź?
Czyli czy np.
Czy pętla daje nam złożoność rzędu \(\displaystyle{ n}\)?
Czy pętla w pętli to złożoność rzędu \(\displaystyle{ n^{2}}\)?

Z góry dziękuję za odpowiedź
Ostatnio zmieniony 14 mar 2012, o 15:04 przez Afish, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.

gryxon
Użytkownik
Użytkownik
Posty: 311
Rejestracja: 30 gru 2011, o 02:21
Płeć: Mężczyzna
Lokalizacja: Puławy
Podziękował: 11 razy
Pomógł: 53 razy

[Algorytmy] Sposoby na obliczanie złożoności algorytmu

Post autor: gryxon » 14 mar 2012, o 00:45

Nie wiem o jak bardzo skomplikowanych algorytmach mówisz więc może mój przykład będzie śmieszny za co z góry przepraszam.
PAV38 pisze: Czyli czy np.
Czy pętla daje nam złożoność rzędu \(\displaystyle{ n}\)?
Czy pętla w pętli to złożoność rzędu \(\displaystyle{ n^{2}}\)?
Dobrym kontrprzykładem na temat pętli w pętli jest algorytm KMP.
Twoje dwie uniwersalne metody bardzo często się sprawdzają ale zawsze należy oszacować maksymalne "przebiegi pętli" w algorytmie i na podstawie tych oszacowań wystawić złożność czasową.

PAV38
Użytkownik
Użytkownik
Posty: 149
Rejestracja: 24 paź 2010, o 09:50
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 18 razy
Pomógł: 2 razy

[Algorytmy] Sposoby na obliczanie złożoności algorytmu

Post autor: PAV38 » 14 mar 2012, o 12:48

A czy trzeba brać pod uwagę złożoność każdej operacji w pętli?
Np wiedząc że mnożenie ma złożoność kwadratową to czy mnożenie w pętli od 1 do n to złożoność n-kwadrat?

gryxon
Użytkownik
Użytkownik
Posty: 311
Rejestracja: 30 gru 2011, o 02:21
Płeć: Mężczyzna
Lokalizacja: Puławy
Podziękował: 11 razy
Pomógł: 53 razy

[Algorytmy] Sposoby na obliczanie złożoności algorytmu

Post autor: gryxon » 14 mar 2012, o 13:05

Wydaję mi się, żeby to oszacować dobrze trzeba wszystkie operacje sprawdzić. Jednakże podstawowe operacje arytmetyczne takie jak mnożenie nie wykonują się w czasie liniowym. Według mojej wiedzy takie rzeczy traktuje się jako \(\displaystyle{ O(1)}\). Jednakże czas stały nie równy czasowi stałemu . Z tego co mi wiadomo operacje bitowe takie jak przesunięcia bitowe są szybsze. Jednakże ta szybkość nie wpływa chyba na złożność czasową.

PAV38
Użytkownik
Użytkownik
Posty: 149
Rejestracja: 24 paź 2010, o 09:50
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 18 razy
Pomógł: 2 razy

[Algorytmy] Sposoby na obliczanie złożoności algorytmu

Post autor: PAV38 » 14 mar 2012, o 21:13

Kod: Zaznacz cały

funkcja Euclid(a, b)
   // wejście: dwie liczby całkowite a i b,  ; wyjście:  
if   then return a   fi
while   do b !=0 do c:=a(mod b) ;a:=b  ;b:=c    od
return a
Ten algorytm ma podobno złożoność czasową \(\displaystyle{ n^3}\) czemu?

No i mam takie wyjaśnienie: \(\displaystyle{ 2n \cdot n^{2}=n^{3}}\)

gdzie \(\displaystyle{ n^2}\) to złożoność operacji\(\displaystyle{ a mod b}\)

Awatar użytkownika
Errichto
Użytkownik
Użytkownik
Posty: 1630
Rejestracja: 17 mar 2011, o 18:55
Płeć: Mężczyzna
Lokalizacja: Suwałki
Podziękował: 28 razy
Pomógł: 272 razy

[Algorytmy] Sposoby na obliczanie złożoności algorytmu

Post autor: Errichto » 14 mar 2012, o 21:25

Jednakże podstawowe operacje arytmetyczne takie jak mnożenie nie wykonują się w czasie liniowym.
Z tego co dalej piszesz, wynika, że chciałeś napisać "stałym" - co jest prawdą.

Szybkość pojedynczych operacji nie wpływa na złożoność, potwierdzam. Złożoność czasowa to określenie, jakiego rzędu wielkości jest ilość operacji elementarnych (pomijając różne niewielkie stałe).

PAV, ten algorytm nie ma takiej złożoności. Operacja \(\displaystyle{ a \ mod \ b}\) wykonuje się w czasie stałym.
http://pl.wikipedia.org/wiki/Algorytm_Euklidesa - pokazane wyprowadzenie złożoności czasowej.

PAV38
Użytkownik
Użytkownik
Posty: 149
Rejestracja: 24 paź 2010, o 09:50
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 18 razy
Pomógł: 2 razy

[Algorytmy] Sposoby na obliczanie złożoności algorytmu

Post autor: PAV38 » 14 mar 2012, o 21:31

Powiem szczerze, że już się gubię w tym. Nie wiem, jak zabrać się za liczenie tych złożoności. Wg. tego co miałem na wykładzie (i tego jak to rozumiem), bierze się te złożoności poszczególnych operacji. Pozwolę sobie zacytować wykład, wyjaśniający ten przykład:
"Ponieważ za każdym razem jest wykonywane dzielenie w czasie kwadratowym, całkowity czas działania to \(\displaystyle{ O(n^{3})}\)".
W Wy jakbyście to policzyli?

EDIT:
Wykładowca celowo wprowadza nas w błąd?
Bo to co piszecie jest zupełnie inne Mógłby ktoś napisać, jak liczy się takie rzeczy, krok po kroku? Co brać pod uwagę? Jak liczyć pętle itd? Czy sprawdzanie warunków jakoś wpływa na złożoność?

Bo zamotałem się w tym temacie już kompletnie !

Awatar użytkownika
Errichto
Użytkownik
Użytkownik
Posty: 1630
Rejestracja: 17 mar 2011, o 18:55
Płeć: Mężczyzna
Lokalizacja: Suwałki
Podziękował: 28 razy
Pomógł: 272 razy

[Algorytmy] Sposoby na obliczanie złożoności algorytmu

Post autor: Errichto » 14 mar 2012, o 21:44

Wykładowca powiedział, że algorytm Euklidesa ma \(\displaystyle{ O(n^3)}\)?
Mocno upraszczając:
Masz pętlę, wewnątrz której jest kilka działań "elementarnych" czyli dzielenie, dodawanie, sprawdzanie (if) itp. Pętla wykonuje się \(\displaystyle{ n}\) razy (np. mamy for(int i=0;i<n;i++) ) - mamy więc \(\displaystyle{ O(n)}\). Przy pętli w pętli mnożymy to. Przy każdorazowym wykonaniu się zewnętrznej wykonuje się wewnętrzna. Jeśli każda wygląda tak: for(int i=0;i<n;i++) to mamy \(\displaystyle{ O(n \cdot n)=O(n^2)}\)
Wyższa szkoła jazdy to określanie złożoności algorytmów związanych np. z NWD. Tam często nie wiadomo, ile razy będzie się coś wykonywać. Cóż, trzeba pomyśleć. Zazwyczaj w złożoności będzie wtedy logarytm
No i jest coś takiego jak zliczanie maksymalnej ilości uruchomień pętli. Coś o tym napisał gryxon. Najlepiej znajdź omówienie tego w książce porządnej.

PAV38
Użytkownik
Użytkownik
Posty: 149
Rejestracja: 24 paź 2010, o 09:50
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 18 razy
Pomógł: 2 razy

[Algorytmy] Sposoby na obliczanie złożoności algorytmu

Post autor: PAV38 » 14 mar 2012, o 21:49

Mhm.. i to co odpisałeś tu, to liczenie złożoności czasowej tak?
Hmm kompletnie inna koncepcja xD Ale pokrywa się z tym, co mniej więcej mi się wydawało. A są jakieś triki na liczenie tych przebiegów pętli które nie zależą od N (while)? Tzn. jakieś popularne metody na szacowanie takich rzeczy? Np. rozpisywanie kilku przykładów krok po kroku, żeby zobaczyć zależność?

Awatar użytkownika
Errichto
Użytkownik
Użytkownik
Posty: 1630
Rejestracja: 17 mar 2011, o 18:55
Płeć: Mężczyzna
Lokalizacja: Suwałki
Podziękował: 28 razy
Pomógł: 272 razy

[Algorytmy] Sposoby na obliczanie złożoności algorytmu

Post autor: Errichto » 14 mar 2012, o 21:55

Tak, to jest liczenie złożoności czasowej.
Można jakieś tam triki próbować stosować... nie czuję się kompetentny do szerszego rozpisywania się - jak już pisałem książka może się przydać. Albo wykładowca / korepetytor / net.

PAV38
Użytkownik
Użytkownik
Posty: 149
Rejestracja: 24 paź 2010, o 09:50
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 18 razy
Pomógł: 2 razy

[Algorytmy] Sposoby na obliczanie złożoności algorytmu

Post autor: PAV38 » 14 mar 2012, o 22:09

Kod: Zaznacz cały

Mamy dwie liczby x, y >= 0. Oraz x>y.
Algorytm zwraca iloczyn tych liczb.
z=0
if y=0 then return z
while y != 0 do
 if (y mod2) != 0 then z= z+x fi
 y = y div 2
 x = 2x od
return z
A to jaką to ma złożoność?

Jest to algorytm Al Khwarizmiego. Mówiąc w skrócie dzielimy \(\displaystyle{ y}\) tak długo, aż będzie równe jeden. Jednocześnie w kolumnie obok wymnażamy \(\displaystyle{ x}\) razy dwa. Na końcu skreślamy wiersze w których \(\displaystyle{ y}\) było parzyste. Wynik to suma kolumny \(\displaystyle{ x}\).

Kod: Zaznacz cały

17 23
8 46
4 92
2 184
1 368
z = 268+23 = 394
Czyli pętla wykona się \(\displaystyle{ \frac{y}{2}}\) razy. W pętli mamy kilka operacji - \(\displaystyle{ c}\). Czyli \(\displaystyle{ c\frac{y}{2}}\). Więc ostateczna odpowiedź to \(\displaystyle{ O(n)}\)- czyli złożoność czasowa rośnie liniowo w stosunku do liczb na wejściu. Czy taka jest złożoność?
Ostatnio zmieniony 15 mar 2012, o 13:00 przez Afish, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.

gryxon
Użytkownik
Użytkownik
Posty: 311
Rejestracja: 30 gru 2011, o 02:21
Płeć: Mężczyzna
Lokalizacja: Puławy
Podziękował: 11 razy
Pomógł: 53 razy

[Algorytmy] Sposoby na obliczanie złożoności algorytmu

Post autor: gryxon » 14 mar 2012, o 23:29

Errichto pisze:Cytuj:Jednakże podstawowe operacje arytmetyczne takie jak mnożenie nie wykonują się w czasie liniowym.
; P
Co to tego algorytmu to mogę się mylić. Jak już powiedział kolega Errichto ( mogę ? ) złożności to dosyć rozległy termin.
Ja bym to zrobił tak:
W każdym przebiegu pętli y jest dzielone przez dwa. Tak więc złożność bym określił na:
\(\displaystyle{ O(log_{2}\ y)}\)

PAV38
Użytkownik
Użytkownik
Posty: 149
Rejestracja: 24 paź 2010, o 09:50
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 18 razy
Pomógł: 2 razy

[Algorytmy] Sposoby na obliczanie złożoności algorytmu

Post autor: PAV38 » 15 mar 2012, o 10:04

Tak masz rację

Kod: Zaznacz cały

z=0;
x=0;
Dzielenie(x,y)
while(x>y) do
  x=x-y;
  i = i+1;
 od
return i;
return z;
A algorytm dzielenia dwóch liczb?
Pętla wykona się \(\displaystyle{ \frac{x}{y}}\) razy. Im bliższe liczby x i y tym pętla wykona się mniej razy. Przypadkiem pesymistycznym będzie sytuacja gdy x będziemy dzielić przez jeden (lub ogólnie coś bardzo małego). Będzie trzeba wykonać x odejmowań i x dodawań jedynki do i. Czy złożoność tego algorytmu będzie liniowa? Tzn ograniczona od góry przez coś liniowego?
\(\displaystyle{ O(x)}\)

Awatar użytkownika
Errichto
Użytkownik
Użytkownik
Posty: 1630
Rejestracja: 17 mar 2011, o 18:55
Płeć: Mężczyzna
Lokalizacja: Suwałki
Podziękował: 28 razy
Pomógł: 272 razy

[Algorytmy] Sposoby na obliczanie złożoności algorytmu

Post autor: Errichto » 15 mar 2012, o 16:14

Oczywiście nie zobaczyłem "nie", wybacz.
Możesz

Jbc. potwierdzam, że pierwszy algorytm ma złożoność \(\displaystyle{ O( \log y)}\)

Jeśli \(\displaystyle{ x}\) oraz \(\displaystyle{ y}\) są zmiennymi wczytywanymi na wejściu to taką złożoność określamy jako \(\displaystyle{ O( \frac{x}{y} )}\). Przecież przy braniu pesymistycznego \(\displaystyle{ y}\), powinieneś też wziąć pesymistyczne \(\displaystyle{ x}\) czyli zapewne górną granicę danego typu danych

PAV38
Użytkownik
Użytkownik
Posty: 149
Rejestracja: 24 paź 2010, o 09:50
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 18 razy
Pomógł: 2 razy

[Algorytmy] Sposoby na obliczanie złożoności algorytmu

Post autor: PAV38 » 15 mar 2012, o 17:36

mhm no ok rozumiem

A jak będzie wyglądało obliczanie złożoności obliczeniowej tego algorytmu? Czym to się różni (w sensie rachunkowym) od liczenia złozoności czasowej?

ODPOWIEDZ