Witam, korzystając z książki Thomasa Cormena "Wprowadzenie do algorytmów" na str 83 zrozumiałem mniej więcej jak rozwiązać to równanie metodą iteracyjną :
\(\displaystyle{ T(n) = 3T\left( \frac{n}{4} \right) +n}\)
I teraz mam problem z rozwiązaniem równania podobnego:
\(\displaystyle{ T(n) = 3T\left( \frac{n}{2} \right) +n}\)
Czy ktoś byłby w stanie wytłumaczyć mi jak je rozwiązać? Dziękuję z góry za pomoc.
Obliczanie złożoności równania rekurencyjnego
- Igor V
- Użytkownik
- Posty: 1605
- Rejestracja: 16 lut 2011, o 16:48
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 18 razy
- Pomógł: 604 razy
Re: Obliczanie złożoności równania rekurencyjnego
Nie mam Cormena natomiast mógłbyś napisać czego nie rozumiesz, przedstawić to co zrobiłeś do tej pory. Musisz zobaczyć jak Ci się układają te wzory, żeby znaleźć zależność i zstępować do warunku początkowego.