Już poprawiłem .
Równanie które podała Poszukujaca, bardziej pasuje do sortowania przez scalanie
natomiast to które ja podałem bardziej przypomina rekurencję tzw sortowania szybkiego
Rekurencje - metoda iteracyjna
-
arek1357
- Użytkownik
- Posty: 5747
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 130 razy
- Pomógł: 526 razy
Rekurencje - metoda iteracyjna
Dla \(\displaystyle{ k=n}\) mamy:
(1) \(\displaystyle{ T(n)=T(n-1)+n+1}\)
\(\displaystyle{ \sum_{n=2}^{ \infty }T(n)x^n=x \sum_{n=2}^{ \infty }T(n-1)x^{n-1}+ \sum_{n=2}^{ \infty }(n+1)x^n=}\)
\(\displaystyle{ S_{n}(x)-1=xS_{n}(x)+ \sum_{n=2}^{ \infty }nx^n+ \sum_{n=2}^{ \infty }x^n=}\)
\(\displaystyle{ S_{n}(x)-1=xS_{n}(x)+ x\sum_{n=2}^{ \infty }nx^{n-1}+ \frac{x^2}{1-x}=}\)
\(\displaystyle{ S_{n}(x)-1=xS_{n}(x)+ x\left[ \sum_{n=2}^{ \infty }x^n\right]' + \frac{x^2}{1-x}=}\)
\(\displaystyle{ S_{n}(x)-1=xS_{n}(x)+ x\left( \frac{x^2}{1-x}\right)' + \frac{x^2}{1-x}=}\)
\(\displaystyle{ S_{n}(x)(1-x)=1+x+\frac{x^2}{1-x}+x\left( \frac{x^2}{1-x}\right)'}\)
i po skróceniach:
\(\displaystyle{ S_{n}(x)= \frac{1-2x+4x^2-2x^3}{(1-x)^3}}\)
o ile się gdzieś nie pomyliłem
Pewnie że się pomyliłem już poprawiłem...
\(\displaystyle{ S_{n}= \sum_{}^{} \frac{1}{2}(n^2+3n-2)x^n}\)
\(\displaystyle{ T(n)=\frac{1}{2}(n^2+3n-2)}\)
Po podstawieniu do (1) wzoru pasuje.
(1) \(\displaystyle{ T(n)=T(n-1)+n+1}\)
\(\displaystyle{ \sum_{n=2}^{ \infty }T(n)x^n=x \sum_{n=2}^{ \infty }T(n-1)x^{n-1}+ \sum_{n=2}^{ \infty }(n+1)x^n=}\)
\(\displaystyle{ S_{n}(x)-1=xS_{n}(x)+ \sum_{n=2}^{ \infty }nx^n+ \sum_{n=2}^{ \infty }x^n=}\)
\(\displaystyle{ S_{n}(x)-1=xS_{n}(x)+ x\sum_{n=2}^{ \infty }nx^{n-1}+ \frac{x^2}{1-x}=}\)
\(\displaystyle{ S_{n}(x)-1=xS_{n}(x)+ x\left[ \sum_{n=2}^{ \infty }x^n\right]' + \frac{x^2}{1-x}=}\)
\(\displaystyle{ S_{n}(x)-1=xS_{n}(x)+ x\left( \frac{x^2}{1-x}\right)' + \frac{x^2}{1-x}=}\)
\(\displaystyle{ S_{n}(x)(1-x)=1+x+\frac{x^2}{1-x}+x\left( \frac{x^2}{1-x}\right)'}\)
i po skróceniach:
\(\displaystyle{ S_{n}(x)= \frac{1-2x+4x^2-2x^3}{(1-x)^3}}\)
o ile się gdzieś nie pomyliłem
Pewnie że się pomyliłem już poprawiłem...
\(\displaystyle{ S_{n}= \sum_{}^{} \frac{1}{2}(n^2+3n-2)x^n}\)
\(\displaystyle{ T(n)=\frac{1}{2}(n^2+3n-2)}\)
Po podstawieniu do (1) wzoru pasuje.
-
Mariusz M
- Użytkownik
- Posty: 6908
- Rejestracja: 25 wrz 2007, o 01:03
- Płeć: Mężczyzna
- Lokalizacja: 53°02'N 18°35'E
- Podziękował: 2 razy
- Pomógł: 1246 razy
Rekurencje - metoda iteracyjna
Powinna się różnić jedynie o stałą od tego co już rozwiązałeś \(\displaystyle{ k=2}\) czyli
w notacji \(\displaystyle{ O}\) nie będzie różnicy
Natomiast dla \(\displaystyle{ k=n}\) mamy \(\displaystyle{ O\left( n^2\right)}\)
Algorytm zwalnia gdy funkcja dzieląca tworzy podtablicę o jednym elemencie dla większości podziałów
w notacji \(\displaystyle{ O}\) nie będzie różnicy
Natomiast dla \(\displaystyle{ k=n}\) mamy \(\displaystyle{ O\left( n^2\right)}\)
Algorytm zwalnia gdy funkcja dzieląca tworzy podtablicę o jednym elemencie dla większości podziałów
-
arek1357
- Użytkownik
- Posty: 5747
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 130 razy
- Pomógł: 526 razy
Rekurencje - metoda iteracyjna
i teraz jeśli podstawimy:
\(\displaystyle{ m= \frac{n}{k}}\)
Otrzymamy ten wzór w postaci:
\(\displaystyle{ T(mk)=T(mk-m)+T(m)+mk}\)
dla \(\displaystyle{ m=1}\)
\(\displaystyle{ T(k)=T(k-1)+k+1}\)
a jawny już powyżej zrobiony,
I trzeba by szukać dla kolejnych:
\(\displaystyle{ m=2,3,4,...}\)
\(\displaystyle{ T(2k)=T(2k-2)+2k+T(2)}\)
i tak dalej:
\(\displaystyle{ T_{i}(ik)=T_{i}(ik-i)+T_{i}(i)+ik}\)
\(\displaystyle{ k}\) - zmienna
żeby dalej brnąć to jeszcze wziąć:
\(\displaystyle{ l=ik}\)
\(\displaystyle{ T(l)=T(l-i)+l+T(i)}\)
\(\displaystyle{ l}\) - zmienna
Teraz pobawić się w funkcje tworzące , i krotne różniczkowanie itd...
\(\displaystyle{ m= \frac{n}{k}}\)
Otrzymamy ten wzór w postaci:
\(\displaystyle{ T(mk)=T(mk-m)+T(m)+mk}\)
dla \(\displaystyle{ m=1}\)
\(\displaystyle{ T(k)=T(k-1)+k+1}\)
a jawny już powyżej zrobiony,
I trzeba by szukać dla kolejnych:
\(\displaystyle{ m=2,3,4,...}\)
\(\displaystyle{ T(2k)=T(2k-2)+2k+T(2)}\)
i tak dalej:
\(\displaystyle{ T_{i}(ik)=T_{i}(ik-i)+T_{i}(i)+ik}\)
\(\displaystyle{ k}\) - zmienna
żeby dalej brnąć to jeszcze wziąć:
\(\displaystyle{ l=ik}\)
\(\displaystyle{ T(l)=T(l-i)+l+T(i)}\)
\(\displaystyle{ l}\) - zmienna
Teraz pobawić się w funkcje tworzące , i krotne różniczkowanie itd...