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

[PAV38]

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ź

[gryxon]

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.

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]

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]

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]

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}\)

[Errichto]

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.
- pokazane wyprowadzenie złożoności czasowej.

[PAV38]

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 !

[Errichto]

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]

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ść?

[Errichto]

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]

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ść?

[gryxon]

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]

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)}\)

[Errichto]

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]

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?