Równanie rekurencyjne

0

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

0

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:
T(n)=\left{ \begin{matrix} \ \Theta (1) &amp;: 1&lt;= n &lt; b\ \ a\cdot T(\frac{n}{b}) + f(n)&amp;:n&gt;= b \end{matrix} \right.

To (gdzie \epsilon to stała > 0 i c to stała z zakresu (0, 1)) :
Jeżeli f(n) \in O(n<sup>{log_ba-\epsilon}) to T(n) \in \Theta (n</sup>{log_ba})
Jeżeli f(n) \in \Theta(n<sup>{log_ba}), to T(n) \in \Theta (n</sup>{log_ba}\cdot \lg\ n)
Jeżeli f(n) \in \Omega(n^{log_ba+\epsilon}) i a\cdot f(\frac{n}{b})&lt;= c\cdot f(n) to T(n) \in \Theta(f(n))
(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)

1 użytkowników online, w tym zalogowanych: 0, gości: 1