Równania rekurencyjne - jak to ruszyć

[celebes]

To mozesz zrobic z twierdzenia o rekurencji uniwersalnej - jest np. w ksiazce CORMEN'a dokladnie opisane.

a=3
b=3
f(n) = n

\(\displaystyle{ n ^{log _{b}a} = n ^{log _{3}3}=TETA(n)}\)

Teraz sprawdzamy w jakim stosunku jest ten \(\displaystyle{ n ^{log _{b}a}}\) do f(n)=n. Sa one rowne, wiec mozemy zastosowac drugie twierdzenie z twierdzenia o rekurencji uniwersalnej, z ktorej wynika, ze jesli \(\displaystyle{ f(n) = n ^{log _{b}a}}\) to T(n) = TETA(\(\displaystyle{ n ^{log _{b}a}}\)*lgn) = TETA(f(n)*lgn) czyli zlozonosc tej rekurencji to TETA(n*lgn)

\(\displaystyle{ lgn = log _{2}n}\)

[abc666]

bigmen, jeśli ci potrzebny tylko rząd to do wszystkich tych przykładów można stosować tw. o którym mówi celebes. Jeśli chcesz dokładny wynik to do

\(\displaystyle{ T(3^k)=3T(3^{k-1})+n}\)
podstawiamy
\(\displaystyle{ T(3^k)=S(3^k)+an+b}\) i dostajemy
\(\displaystyle{ S(3^k)+an+b=3S(3^{k-1})+3an+3b+n \\
S(3^{k})=3S(3^{k-1})+n(2a+1)+2b}\)
skąd musi zachodzić
\(\displaystyle{ n(2a+1)+2b\equiv 0}\) czyli
\(\displaystyle{ a=-\frac{1}{2}\\
b=0}\)
czyli
\(\displaystyle{ S(3^k)-\frac{1}{2}n=3S(3^{k-1})-\frac{3}{2}n+n\\
S(3^k)=3S(3^{k-1})}\)

[bigmen]

celebes, dzięki za odpowiedź, lecz tak jak pisze abc666, chodzi mi o dokładny wynik.

abc666, metoda którą wyżej pokazałeś jest bardzo czytelna i prosta do zrozumienia - dzięki za przedstawienie jej krok po kroku.

Przerabiając zadania, z racji że nie mam do nich odpowiedzi często posiłkuje się zdaniem Wolframa na ten temat i idąc dalej w tym przykładzie mamy:

\(\displaystyle{ S(3^k)=3S(3^{k-1})=...=3^kS(1)}\)

I wracając do podstawienia:

\(\displaystyle{ T(3^k)=3^kS(1)- \frac{1}{2}n=3^kT(1)- \frac{1}{2}n
\\T(n)=n-\frac{1}{2}n=\frac{1}{2}n}\)

, lecz Wolfram podaje wynik (sprawdzam z jego wynikami, ponieważ do tej pory się nie mylił):

\(\displaystyle{ T(n) = nlog_3{3n}}\)

Czy gdzieś wyżej zrobiłem błąd?

[abc666]

Ajajaj bo nie podstawiłem za wszystkie i stąd ten zły wynik . Tutaj będzie trochę inaczej

\(\displaystyle{ T(3^k)=3T(3^{k-1})+3^k}\)
teraz dzielimy stronami przez \(\displaystyle{ 3^{k}}\)
\(\displaystyle{ \frac{T(3^k)}{3^k}=\frac{3T(3^{k-1})}{3^k}+1=\frac{T(3^{k-1})}{3^{k-1}}+1}\)

I jeśli teraz podstawimy
\(\displaystyle{ S(k)=\frac{T(3^k)}{3^k}}\)
dostaniemy
\(\displaystyle{ S(k)=S(k-1)+1=S(k-2)+2=...=S(0)+k}\)
gdy teraz wrócimy do ostatniego podstawienia mamy
\(\displaystyle{ \frac{T(3^k)}{3^k}=\frac{T(3^0)}{3^0}+k=T(1)+k=k+1}\)
mnożymy razy \(\displaystyle{ 3^{k}}\)
\(\displaystyle{ T(3^k)=3^k\cdot k+3^k}\)
wracamy z podstawieniem i mamy
\(\displaystyle{ T(n)=n\cdot \log _ {3}n+n=n( \log _ {3}n+1)=n( \log _ {3}n+ \log _ {3}3)=n\cdot \log _ {3} 3n}\)

Tutaj zastosowałem inny sposób. Jest to prosty przykład wykorzystania czynnika sumacyjnego. Tamten wcześniejszy sposób jest tutaj kłopotliwy ponieważ \(\displaystyle{ 3}\) jest pierwiastkiem równania charakterystycznego i przy podstawieniu trzeba domnożyć wszystko przez \(\displaystyle{ n}\) co nie ma tak oczywistego uzasadnienia. Ale widać, że czynnik sumacyjny w tym przypadku bardzo szybko prowadzi do odpowiedzi. Jak to dokładniej wygląda możesz zobaczyć tutaj 252307.htm#p949428.

p.s. Jak widać lepiej nie zostawiać tak dwóch zmiennych w równaniu bo powoduje to błędy. Jak podstawiamy to już za wszystko.

[bigmen]

Ok, dzięki za kolejną metodę.

Jeśli w: \(\displaystyle{ T(3^k)=3T(3^{k-1})+3^k}\) nie byłoby 3 przed T, to wtedy to dzielenie przez 3 nic nam nie da?

Bo mając taki oto przykład (myślę że już ostatni w tym temacie ):

\(\displaystyle{ T(n)=T(n/2)+n, T(1)=1}\)

Korzystając z tej metody z wielomianem, nie da się dobrać współczynników tak, aby to n się nam zredukowało.

Próbując, natomiast dzielić przez \(\displaystyle{ 2^k}\), tak jak w przykładzie wyżej, otrzymamy:
\(\displaystyle{ \frac{T(2^k)}{2^k}=\frac{T(2^{k-1})}{2^k}+1}\), i tutaj S(k) sobie chyba nie podstawimy?

[abc666]

Te podstawienia mają właśnie na celu wyeliminowanie tych współczynników, które stoją przed \(\displaystyle{ T}\). Skoro tutaj ich nie a to sprawa jest nawet prostsza.

Po podstawieniu \(\displaystyle{ n=2^k}\) mamy
\(\displaystyle{ T(2^k)=T(2^{k-1})+2^k=...=T(2^{0})+2^1+2^2+...+2^k}\)

A to liczymy ze zwykłego wzoru na sumę ciągu geometrycznego.

[bigmen]

Jeszcze raz dzięki za pomoc. Temat może zostać zamknięty.

Teraz pozostaje tylko wykorzystać tą wiedzę na egzaminie.

Pozdrawiam.