Obliczanie złożoności równania rekurencyjnego

Lextar
Użytkownik
Użytkownik
Posty: 1
Rejestracja: 19 lis 2017, o 12:56
Płeć: Mężczyzna
Lokalizacja: Kraków

Obliczanie złożoności równania rekurencyjnego

Post autor: Lextar »

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.
Awatar użytkownika
Igor V
Użytkownik
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

Post autor: Igor V »

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.
ODPOWIEDZ