Witam! Proszę o pomoc, jutro mam kolokwium i będę miał coś takiego jutro i nie mam pojęcia jak to zrobić.
Rozwiąż równanie rekurencyjne (metoda dowolna)
T(n)=4T(n/4)+ n^2
słownie:
(n/4) <-- n przez 4 (po prostu ułamek)
n^2 <-- n do potęgi 2
Witam! Proszę o pomoc, jutro mam kolokwium i będę miał coś takiego jutro i nie mam pojęcia jak to zrobić.
Rozwiąż równanie rekurencyjne (metoda dowolna)
T(n)=4T(n/4)+ n^2
słownie:
(n/4) <-- n przez 4 (po prostu ułamek)
n^2 <-- n do potęgi 2
Równania rekurencyjne w takiej formie najprościej rozwiązywać z rekurencji uniwersalnej - rozwiązanie sprowadza się do podstawienia do wzoru:
http://pl.wikipedia.org/wiki/Twierdzenie_o_rekurencji_uniwersalnej
Czyli że jeśli masz funkcję w formie:
To (gdzie to stała > 0 i c to stała z zakresu (0, 1)) :
Jeżeli to
Jeżeli , to
Jeżeli i to
(trochę niewyraźny tutaj tex... Na Wikipedii to ładniej wygląda w każdym razie).
Więcej (pod kątem liczenia złożoności) w Cormenie, chociaż do jutra oczywiście nie zdążysz Cormena przerobić...
(edit - cóż, wyprzedzono mnie)