@wiwiwi: Po pierwsze w tym wypadku nie chcesz mnożyć T(n-1) tylko je do siebie dodać. Czyli T(n) = 2 * T(n-1) = 2 * (2 * T(n-2)) = ... = 2^n T(0) = 2^n bo T(0) = 1
EDIT: Przy obliczaniu zignorowałem operację mnożenia. Nie wiem co ma dokładnie wyliczyć Twoja funkcja i czy ma liczyć dokładnie, czy w notacji O.
Jeśli ma liczyć dokładnie to w każdym równananiu musisz dodać
Ktoś wie jak rozwiązać to równanie?
#algorytmy #analizaalgorytmow #programowanie
po zlogarytmowaniu wyjdzie
lgT(n) = 2lgT(n-1) tylko nie wiem co dalej
algorytm wygląda następująco
funkcja J (n) {
if(n==0) J = 1
else J = J(n-1)*J(n-1)
}
może miałbyś jakiś pomysł
Czyli T(n) = 2 * T(n-1) = 2 * (2 * T(n-2)) = ... = 2^n T(0) = 2^n
bo T(0) = 1
EDIT: Przy obliczaniu zignorowałem operację mnożenia. Nie wiem co ma dokładnie wyliczyć Twoja funkcja i czy ma liczyć dokładnie, czy w notacji O.
Jeśli ma liczyć dokładnie to w każdym równananiu musisz dodać
J(0) = 1
J(n) = (J(n - 1))^2
J(n - 1) = ((J(n - 2)^2)^2 => ((J(n-2)))^4
z tego widac, ze zlozonosc to O(2^n)
J(3) = J(2)^2 = J(1)^2^2 = J(0)^2^2^2 = 1^2^2^2 = 1
@dagon_666:
Chodzi o to, zeby sie pozbyc rekurencji
J(0) wykonuje sie w czasie stalym.
T(0) = J(0) = C
Ogolny przypadek:
T(n) = (T(n - 1))^2
podstawiajac rekurencyjnie n - 1 za n:
=> (T(n-2))^4
=> (T(n-3))^8
zatem:
=> (T(n - k))^(2^k)
sprowadzajac do przypadku podstawowego:
n - k = 0, zatem n = k
otrzymujemy:
T(0) = (T(0))^(2^n)
T(0) = C, zatem T(0) = C^(2^n)
z czego wynika O(2^n)