.

. asdf: Witam emotka

Równanie rekurencyjne: Mam takie równanie rekurencyjne T(n), dla n = log_bn, i mam zbadać θ (czasochłonność algorytmu) dla przypadków: a > b, a = b, a < b

	⎧	c, n=1
T(n) =	⎩	a*T(ⁿ_b) + cn, n>1

no to liczę:

	n
T(n) = a * T(		) + cn =
	b

n 
b 

n

n

a * (a*T(

) + cn) + cn = a * (a*T(

) + c

) + cn =

b

b2

b

	n		cna
a²*T(		) +		+ cn =
	b²		b

	n		a
a²*T(		) + cn(		+ 1) =
	b²		b

	n		n		a
a²(aT(		) +c*		) + cn(		+ 1) =
	b³		b²		b

	n		na²		a
a³*T(		) +c*		) + cn(		+ 1) =
	b³		b²		b

	n		a²		a
a³*T(		) +cn*		) + cn(		+ 1) =
	b³		b²		b

	n		a²		a
a³*T(		) +cn(		+		+ 1) =
	b³		b²		b

....

	n		a^k−1		a¹		a⁰
a^k*T⁽		) + cn(		+ .. +		+		)
	b^k		b^k−1		b¹		b⁰

piersza część: dla k = log_bn ⇒ b^k = n

	[c[b^k]		a^k−1		a¹		a⁰
a^k*T⁽		) + cn(		+ .. +		+		) =
	b^k		b^k−1		b¹		b⁰

	a^k−1		a¹		a⁰
a^k*T⁽1) + cn(		+ .. +		+		) =
	b^k−1		b¹		b⁰

T(1) = c, czyli:

	a^k−1		a¹		a⁰
a^k*c + cn(		+ .. +		+		) =
	b^k−1		b¹		b⁰

−−−−−−−−−−−−−

	n
n = b^k, czyli		= 1, c*1 = c
	b^k

−−−−−−−−−−−−−

	n		a^k−1		a¹
a^kc		+ cn(		+ .. +		+ 1) =
	b^k		b^k−1		b¹

	a^k		a^k−1		a¹
cn(		+		+ .. +		+ 1)
	b^k		b^k−1		b¹

kolejna część: a = b cn(1 + 1 + ... + 1) = cn(k + 1), czy samo cn*k? (wydaje mi się, że k+1, ale nie jestem tego właśnie pewien

), ale i tak tutaj to będzie liniowe?: cn, czyli θ(n)? kolejna część: a < b

	a^k		a^k−1		a¹
cn(		+		+ .. +		+ 1)
	b^k		b^k−1		b¹

	a^k
lim_k→∞(		) = 0, ale jest to suma ciągu, więc jeżeli a > b, a nie wiadomo o jak dużo
	b^k

jest to większe, więc są to już tak małe wartości, że można je pominąć? zapis: →0 = "dąży do zera" cn(→ 0 + → 0 + ...+ → 0 + 1) = cn *1 = cn i wychodzi mi czasochłonność algorytmu liniowa, a w odpowiedzi jest: θ(n*log_bn), gdy a = b kolejna część: a > b, tego nie wiem jak zrobić

	a^k		a^k−1		a¹
cn(		+		+ .. +		+ 1)
	b^k		b^k−1		b¹

..

asdf: :(?

asdf: :(

!11jedenjeden

Subi: może nie pomogę ale mam pytanie: czy równania redukcyjne mogą zdarzyć się na maturze rozszerzonej?

asdf: a nie wiem, nie pisałem rozszerzonej matematyki, więc też nie pomogę

Ale na pewno nie takie równania rekurencyjne − te jest zbyt trudne.

LoL2o10: Moga.

Mateusz: Nie, na maturze z matematyki nie ma równan rekurencyjnych rekurencja zazwyczaj moze wystąpic na maturze z informatyki ale bedzie sie to zazwyczaj odnosiło do rozpisania drzewka wywołań czy odgadniecia ogolnego wzoru.

Trivial:

a
	→ 0 ? Ciekawe...
b

Trivial:

	n
T(n) = aT(		) + cn
	b

	n		a
= a²T(		) +		cn + cn
	b²		b

	n		a²		cn
= a³T(		) +		cn +		cn + cn
	b³		b²		b

	n		a³		a²		cn
= a⁴T(		) +		cn +		cn +		cn + cn
	b⁴		b³		b²		b

	n
= a⁴T(		) + (^a_b)³cn + (^a_b)²cn + (^a_b)cn + cn
	b⁴

	n
= a^kT(		) + cn*((^a_b)^k−1 + ... + (^a_b) + 1)
	b^k

	n		(^a_b)^k−1
= a^kT(		) + cn*
	b^k		(^a_b)−1

Podstawiamy n = b^k i mamy:

	(^a_b)^k−1
T(n) = a^kT(1) + cn*
	u−1

	(^a_b)^log_bn−1
= c(a^log_bn + n		)
	^a_b−1

alogbn 
−1
n 

        = c*(alogbn + n*

)

  ab−1

	a^log_bn−n
= c*(a^log_bn +		)
	^a_b−1

	b		b
= c*(a^log_bn +		*a^log_bn−		*n)
	a−b		a−b

	c
=		*(a^1+log_bn − bn)
	a−b

Trivial: A dla przypadku a = b:

	n
T(n) = a^kT(		) + cn*((^a_b)^k−1 + ... + (^a_b) + 1)
	b^k

	n
= a^kT(		) + cn*(1 + 1 + ... + 1)
	a^k

	n
= a^kT(		) + ckn
	a^k

= a^log_anT(1) + cnlog_an = cn + cnlog_an = cn(1+log_an) = Θ(nlog_an)