Uczę się obliczania złożoności algorytmów z książki Thomasa Cormena "Wprowadzenie do algorytmów". Na str. 83 jest podany przykład rekurencji i rozwiązanie jej metodą iteracyjną, tyle że nie mogę zrozumieć o co chodzi w tej iteracji. Oto przykład:
\(\displaystyle{ T(n) = 3T\left( \frac{n}{4} \right) +n}\)
Iterujemy ją następująco:
\(\displaystyle{ T(n) = n+3T\left( \frac{n}{4} \right) = n+3\left( \frac{n}{4}+3T\left( \frac{n}{16} \right) \right) = n+3\left( \frac{n}{4}+3\left( \frac{n}{16}+3T\left( \frac{n}{64} \right) \right) \right= n + \frac{3n}{4} + \frac{9n}{16} +27T\left( \frac{n}{64} \right)}\)
Byłbym wdzięczny gdyby ktoś w prosty sposób wytłumaczył mi na czym polega ta iteracja i jak z niej wywnioskować złożoność algorytmu. Pozdrawiam
Obliczanie złożoności algorytmu rekurencyjnego
-
rudolf35
- Użytkownik
- Posty: 18
- Rejestracja: 10 paź 2007, o 19:38
- Płeć: Mężczyzna
- Lokalizacja: Toruń
- Podziękował: 6 razy
Obliczanie złożoności algorytmu rekurencyjnego
Ostatnio zmieniony 27 mar 2011, o 18:24 przez Lbubsazob, łącznie zmieniany 1 raz.
Powód: Nieczytelny zapis - brak LaTeX-a. Proszę zapoznać się z instrukcją: http://matematyka.pl/latex.htm .
Powód: Nieczytelny zapis - brak LaTeX-a. Proszę zapoznać się z instrukcją: http://matematyka.pl/latex.htm .
-
Fingon
- Użytkownik
- Posty: 222
- Rejestracja: 24 sie 2009, o 02:21
- Płeć: Mężczyzna
- Lokalizacja: Katowice
- Pomógł: 32 razy
Obliczanie złożoności algorytmu rekurencyjnego
Iteracja w tym przypadku to ponowne wykorzystanie wzoru \(\displaystyle{ T(n) = 3T(n/4)+n}\)
Kolejne iteracje:
\(\displaystyle{ T(n) = n + 3T(n/4)}\)
\(\displaystyle{ T(n) = n + 3(n/4 + 3T(n/16))}\)
\(\displaystyle{ T(n) = n + 3(n/4 + 3(n/16 + 3T(n/64)))}\)
...
Ogólnie w kolejnej iteracji zamiast \(\displaystyle{ T(n)}\), podstawiasz \(\displaystyle{ n + 3T(n/4)}\).
Co do wywnioskowania złożoności algorytmu, to po prostu musisz znaleźć wzór jawny lub odpowiednio oszacować \(\displaystyle{ T(n)}\) .
Nie przejmuj się na początku za bardzo rozdziałem o rekurencji, obliczanie złożoności obliczeniowej po poznaniu kilku algorytmów powinno stać się dla Ciebie jasne.
Kolejne iteracje:
\(\displaystyle{ T(n) = n + 3T(n/4)}\)
\(\displaystyle{ T(n) = n + 3(n/4 + 3T(n/16))}\)
\(\displaystyle{ T(n) = n + 3(n/4 + 3(n/16 + 3T(n/64)))}\)
...
Ogólnie w kolejnej iteracji zamiast \(\displaystyle{ T(n)}\), podstawiasz \(\displaystyle{ n + 3T(n/4)}\).
Co do wywnioskowania złożoności algorytmu, to po prostu musisz znaleźć wzór jawny lub odpowiednio oszacować \(\displaystyle{ T(n)}\) .
Nie przejmuj się na początku za bardzo rozdziałem o rekurencji, obliczanie złożoności obliczeniowej po poznaniu kilku algorytmów powinno stać się dla Ciebie jasne.
Ostatnio zmieniony 12 sie 2010, o 17:36 przez Fingon, łącznie zmieniany 1 raz.
-
rudolf35
- Użytkownik
- Posty: 18
- Rejestracja: 10 paź 2007, o 19:38
- Płeć: Mężczyzna
- Lokalizacja: Toruń
- Podziękował: 6 razy
Obliczanie złożoności algorytmu rekurencyjnego
Niestety muszę nauczyć się obliczania złożoności algorytmów rekurencyjnych, żeby zaliczyć egzamin poprawkowy - gdyby nie one to bym miał go do przodu...rudolf35 pisze:Nie przejmuj się na początku za bardzo rozdziałem o rekurencji, obliczanie złożoności obliczeniowej po poznaniu kilku algorytmów powinno stać się dla Ciebie jasne.
Ok, ale nadal nie czuję dlaczego tak trzeba robić. Możesz się trochę bardziej zagłębić...?rudolf35 pisze:Ogólnie w kolejnej iteracji zamiast T(n), podstawiasz n + 3T(n/4)
-
Fingon
- Użytkownik
- Posty: 222
- Rejestracja: 24 sie 2009, o 02:21
- Płeć: Mężczyzna
- Lokalizacja: Katowice
- Pomógł: 32 razy
Obliczanie złożoności algorytmu rekurencyjnego
Rozwijamy po to, żeby pozbyć się \(\displaystyle{ T(n)}\) i obliczyć powstałą po iteracjach sumę.
\(\displaystyle{ T(n) = n + 3T(n/4)}\)
Najniżej możemy zejść do \(\displaystyle{ T(1) = \Theta(1)}\)(to powinno być podane przy wzorze na \(\displaystyle{ T(n)}\)), co wymaga \(\displaystyle{ \log_{4}(n)}\) iteracji.
Patrząc na kolejne iteracje, zauważamy, że
\(\displaystyle{ T(n) = n + \frac{3}{4}n + \frac{3^2}{4^2}n + ... + \frac{3^{\log_4(n)}}{4^{log_4(n)}}\cdot \Theta(1)}\)
Obliczając wartość sumy, która w tym przypadku jest sumą ciągu geometrycznego, mamy wzór jawny na \(\displaystyle{ T(n)}\), czyli złożoność, której szukaliśmy.
\(\displaystyle{ T(n) = n + 3T(n/4)}\)
Najniżej możemy zejść do \(\displaystyle{ T(1) = \Theta(1)}\)(to powinno być podane przy wzorze na \(\displaystyle{ T(n)}\)), co wymaga \(\displaystyle{ \log_{4}(n)}\) iteracji.
Patrząc na kolejne iteracje, zauważamy, że
\(\displaystyle{ T(n) = n + \frac{3}{4}n + \frac{3^2}{4^2}n + ... + \frac{3^{\log_4(n)}}{4^{log_4(n)}}\cdot \Theta(1)}\)
Obliczając wartość sumy, która w tym przypadku jest sumą ciągu geometrycznego, mamy wzór jawny na \(\displaystyle{ T(n)}\), czyli złożoność, której szukaliśmy.