. asdf: Dobry wieczór, twierdzenie o rekurencji uniwersalnej (na razie taki temat o rekurencji uniwersalnej, bo chce dojść do sposobu ich rozwiazywania, ale perw inne przykłady ) Jeżeli mam funkcję rekurencyjną, np.

	n		n		n		n
T(n) = T(		) + C = T(		) + C + C = T(		) + C + C+ C = ... T(		) + k*c
	2		4		8		2k

podane jest też, że: T(1) = C więc sprowadzam to do:

n
	= 1, obliczam z tego k:
2k

2^k = n ⇒ k = log₂n, otrzymuje postać: T(1) + (log₂n)*c = C + c*log₂n, T(n) = θ(C + c*log₂n,) = θ(logn) Dobrze złożoność asymptotyczna jest policzona?

asdf: a za pomocą rekurencji uniwerslanej:

	n
T(		) + C, a = 1, b = 2, f(n) = C
	2

log_ba = log₂1 = 0 n⁰ = 1 i co w związku z tym? jak zastosowac tą rekurencje uniwersalną?

asdf: to będzie takie coś? f(n) = C = θ(1)? n⁰ = 1, czyli θ(logn)?

Trivial: http://pl.wikipedia.org/wiki/Rekurencja_uniwersalna T(n) = T(n/2) + C log_ba = log₂1 = 0, f(n) = C Mamy 3 przypadki do wyboru: 1. Czy f(n) = O(n^−ε) dla pewnej stałej ε > 0? Nie. 2. Czy f(n) = Θ(n⁰} = Θ(1)? Tak. Stąd T(n) = Θ(logn). 3. ...

asdf: dzieki bardzo

asdf: a masz może jakieś zadania do liczenia złożoności? np. jest jakiś alogorytm, podać czasu obliczeń każdej operacji a na koncu złożoność obliczyć, np. for i=1:n << T(n+1) tab[i]=c; << T(n) end T(N) = T(n+1) + T(n)= θ(2N) = θ(N)

asdf: jakbyś mógł to wejdź: https://matematykaszkolna.pl/forum/180494.html spróbuje coś rozwiązać

asdf: albo jednak tu będę pisać:

	n
T(n) = 16T(		) + n
	4

a = 16, b = 4, f(n) = n = θ(n) n^log_ba = n² n¹ =? n² 1 < 2, więc tutaj trzeba użyć pierwszego czy trzeciego wzoru? bo mam: n^{1 + e} = n² (e=1) ale też mogę użyć: n¹ = n^2−e (e=1) i który tutaj wzór?

Trivial: Jesteś?

asdf: ?

asdf: a miałbyś chwile, zeby zrobić kilka rpostych zadań? (godzinka starczy max)

Trivial: Mam czas.

asdf: http://collabedit.com/v774t