[Algorytmy] Sposoby na obliczanie złożoności algorytmu
-
- 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
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ź
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.
Powód: Poprawa wiadomości.
-
- 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
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.
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ą.
Dobrym kontrprzykładem na temat pętli w pętli jest algorytm KMP.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}}\)?
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ą.
-
- 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
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?
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?
-
- 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
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ą.
-
- 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
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
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
- Użytkownik
- Posty: 1629
- 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
Z tego co dalej piszesz, wynika, że chciałeś napisać "stałym" - co jest prawdą.Jednakże podstawowe operacje arytmetyczne takie jak mnożenie nie wykonują się w czasie liniowym.
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.
-
- 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
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 !
"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
- Użytkownik
- Posty: 1629
- 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
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.
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.
-
- 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
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ść?
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
- Użytkownik
- Posty: 1629
- 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
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.
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.
-
- 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
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
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
Ostatnio zmieniony 15 mar 2012, o 13:00 przez Afish, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
-
- 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
; PErrichto pisze:Cytuj:Jednakże podstawowe operacje arytmetyczne takie jak mnożenie nie wykonują się w czasie liniowym.
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)}\)
-
- 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
Tak masz rację
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)}\)
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;
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
- Użytkownik
- Posty: 1629
- 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
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
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
-
- 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
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?
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?