Witam
mam taki problem, pytanie brzmi:
Podać rozwiązania równań rekurencyjnych:
T(n) = b, dla n = 1, oraz
T(n) = aT(n/c) + bn, dla n > 1.
Podać interpretację rozwiązań.
Z góry dziękuje za Pomoc.
0
0
i gdzie konkretnie masz problem?
0
hmm problem konkretnie tkwi w rozwiązaniu tej rekurencji :)
0
masz to zaimplementować, uprościć czy co?
0
Ma to policzyć. W Cormenie masz wyjaśnienie jak się to robi...
0
rekurencji się nie rozwiązuje.
sprawdź, co dzieje się na n=1, zapisz wynik. linijkę niżej sprawdź, co dzieje się na n=2, zapisz wynik. linijkę niżej sprawdź, co się dzieje dla n=3, zapisz wynik... jednocześnie zastanów się, czy dla pewnych wartości a, b, c nie zajdzie jakiś nieprawidłowy przypadek - dzielenie przez 0, podanie niezdefiniowanej wartości itp.
wersja dla niekumatych:
n=1 | | T(1) = b
n=2 | | T(2) = aT(n/c) + bn = aT(2/c) + b2; zakładam, że c Є C;
n=2 | c < 0 | T(n) niezdefiniowane dla ujemnych liczb, błąd
n=2 | c = 0 | błąd dzielenia przez 0
n=2 | c = 1 | T(2) = aT(2/c) + b2 = aT(2) + 2b, błąd przepełnienia stosu, teoretycznie dla b≠0 wynik działania to +-∞, zależnie od znaku a; dla b=0 wynik to teoretycznie 0
n=2 | c Є {2, 3, 4} | T(2) = aT(2/c) + b2 = aT(1) + 2b = ab + b2 = b*(a+2)
n=2 | c > 4 | T(2) = aT(2/c) + b2 = aT(0) + 2b, T(n) niezdefiniowane dla 0, błąd
n=3 | c=2 | sam sobie policz
n=3 | c Є {3, 4} | sam sobie policz
n=4 | c=2 | T(4) = aT(4/2) + b4 = aT(2) + 4b = a[T(2) obliczone wcześniej dla przypadku c=2]+4b = a*[b*(a+2)] + 4b = b*(a(a+2)+4)
n=4 | c=3 | sam sobie policz
n=4 | c=4 | sam sobie policz
...
dla b=0, z wyjątkiem szczególnych przypadków wartości c opisanych wyżej, T(n) = 0 niezależnie od n.