Rekurencje - metoda iteracyjna
- Poszukujaca
- Użytkownik
- Posty: 2775
- Rejestracja: 21 maja 2012, o 23:32
- Płeć: Kobieta
- Podziękował: 1019 razy
- Pomógł: 166 razy
Rekurencje - metoda iteracyjna
Metodą iteracyjną rozwiązać:
\(\displaystyle{ T(n)= \begin{cases} 1, \ n=1 \\ 2T(\frac{n}{2})+n, \ n>1 \end{cases}}\)
Zrobiłąm na razie tyle: \(\displaystyle{ T(n)=2T(\frac{n}{2})+n=n+2(2t(\frac{n}{4})+\frac{n}{2})=2n+4T(\frac{n}{8})+\frac{n}{4})=3n+8T(\frac{n}{8})=}\)
\(\displaystyle{ = 3n+8(2T(\frac{n}{16})+\frac{n}{8})=}\)
\(\displaystyle{ = 4n+16T(\frac{n}{16})=4n+16(2T(\frac{n}{32})+\frac{n}{16})=5n+32T(\frac{n}{32})}\)
\(\displaystyle{ T(n)= \begin{cases} 1, \ n=1 \\ 2T(\frac{n}{2})+n, \ n>1 \end{cases}}\)
Zrobiłąm na razie tyle: \(\displaystyle{ T(n)=2T(\frac{n}{2})+n=n+2(2t(\frac{n}{4})+\frac{n}{2})=2n+4T(\frac{n}{8})+\frac{n}{4})=3n+8T(\frac{n}{8})=}\)
\(\displaystyle{ = 3n+8(2T(\frac{n}{16})+\frac{n}{8})=}\)
\(\displaystyle{ = 4n+16T(\frac{n}{16})=4n+16(2T(\frac{n}{32})+\frac{n}{16})=5n+32T(\frac{n}{32})}\)
- Poszukujaca
- Użytkownik
- Posty: 2775
- Rejestracja: 21 maja 2012, o 23:32
- Płeć: Kobieta
- Podziękował: 1019 razy
- Pomógł: 166 razy
Rekurencje - metoda iteracyjna
a4karo, \(\displaystyle{ T(2)=2T(1)+2=4, \ T(4)=2T(2)+4=12}\)
Dam radę policzyć tylko wyrazy, które mają indeksy w postaci potęgi dwójek.
Czy to znaczy, że ciąg jest źle zdefiniowany i nie ma takiego ciągu?
Dam radę policzyć tylko wyrazy, które mają indeksy w postaci potęgi dwójek.
Czy to znaczy, że ciąg jest źle zdefiniowany i nie ma takiego ciągu?
- Poszukujaca
- Użytkownik
- Posty: 2775
- Rejestracja: 21 maja 2012, o 23:32
- Płeć: Kobieta
- Podziękował: 1019 razy
- Pomógł: 166 razy
Rekurencje - metoda iteracyjna
Dobrze, pobawię się
Ale czy można stwierdzić, że nie da się przeprowadzić tutaj sensownej iteracji, która doprowadzi do rozwiązania?
Ale czy można stwierdzić, że nie da się przeprowadzić tutaj sensownej iteracji, która doprowadzi do rozwiązania?
- arek1357
- Użytkownik
- Posty: 5740
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 130 razy
- Pomógł: 525 razy
Rekurencje - metoda iteracyjna
tak jak to zrobiłem w linku z przymrużeniem oka...
Najpierw pobaw się z ciągiem:
\(\displaystyle{ x_{1}=1}\)
\(\displaystyle{ x_{n+1}=2x_{n}+2^n}\)
Znajdź wzór jawny
Wyszło mi:
\(\displaystyle{ x_{n}=2^{n-1}n}\)
Teraz: robię takie kwiprokwo:
przypuszczam , że:
\(\displaystyle{ x_{n+1}=T(2^n)=2^n(n+1)}\)
\(\displaystyle{ 2^n=x}\)
\(\displaystyle{ n= \frac{\ln x}{\ln 2}}\)
Dalej sobie brnę w to bagno i obstaję przy tym, że:
potem z powrotem podstawiam:
\(\displaystyle{ x:=n}\)
\(\displaystyle{ T(n)=n \frac{\ln n}{\ln 2}+n}\)
a teraz:
\(\displaystyle{ T(2n)=2n \frac{\ln 2n}{\ln 2}+2n}\)
A teraz sprawdzam, czy:
(1)\(\displaystyle{ T(2n)=2T(n)+2n}\) - czyli wyjściowe nasze
I o dziwo dla:
\(\displaystyle{ T(n)=n \frac{\ln n}{\ln 2}+n}\)
Wzór (1) jest spełniony i działa (sprawdzałem osobiście)
W ten nietypowy sposób poszerzyliśmy wzór z dziedziny potęg dwójki na wszystkie eny a nawet ixy...
czyli ostatecznie:
\(\displaystyle{ T(n)=n \frac{\ln n}{\ln 2}+n , n \in N}\)
lub:
\(\displaystyle{ T(x)=x \frac{\ln x}{\ln 2}+x , x \in R , x>0}\)
Teraz możesz liczyć nie tylko dla potęg dwójki ale i dla wszystkich liczb dodatnich...
Troszkę więcej roboty niż w tym wzorku z linku ponieważ musiałem tworzyć funkcje tworzące
dla wyznaczenia wzoru jawnego...
Tak do końca nie musicie brać tego na poważnie...
Najpierw pobaw się z ciągiem:
\(\displaystyle{ x_{1}=1}\)
\(\displaystyle{ x_{n+1}=2x_{n}+2^n}\)
Znajdź wzór jawny
Wyszło mi:
\(\displaystyle{ x_{n}=2^{n-1}n}\)
Teraz: robię takie kwiprokwo:
przypuszczam , że:
\(\displaystyle{ x_{n+1}=T(2^n)=2^n(n+1)}\)
\(\displaystyle{ 2^n=x}\)
\(\displaystyle{ n= \frac{\ln x}{\ln 2}}\)
Dalej sobie brnę w to bagno i obstaję przy tym, że:
potem z powrotem podstawiam:
\(\displaystyle{ x:=n}\)
\(\displaystyle{ T(n)=n \frac{\ln n}{\ln 2}+n}\)
a teraz:
\(\displaystyle{ T(2n)=2n \frac{\ln 2n}{\ln 2}+2n}\)
A teraz sprawdzam, czy:
(1)\(\displaystyle{ T(2n)=2T(n)+2n}\) - czyli wyjściowe nasze
I o dziwo dla:
\(\displaystyle{ T(n)=n \frac{\ln n}{\ln 2}+n}\)
Wzór (1) jest spełniony i działa (sprawdzałem osobiście)
W ten nietypowy sposób poszerzyliśmy wzór z dziedziny potęg dwójki na wszystkie eny a nawet ixy...
czyli ostatecznie:
\(\displaystyle{ T(n)=n \frac{\ln n}{\ln 2}+n , n \in N}\)
lub:
\(\displaystyle{ T(x)=x \frac{\ln x}{\ln 2}+x , x \in R , x>0}\)
Teraz możesz liczyć nie tylko dla potęg dwójki ale i dla wszystkich liczb dodatnich...
Troszkę więcej roboty niż w tym wzorku z linku ponieważ musiałem tworzyć funkcje tworzące
dla wyznaczenia wzoru jawnego...
Tak do końca nie musicie brać tego na poważnie...
- arek1357
- Użytkownik
- Posty: 5740
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 130 razy
- Pomógł: 525 razy
Rekurencje - metoda iteracyjna
A teraz proszę przetłumacz mi to na nasze, ja człowiek bardzo prosto myślący nie dla mnie takie indygacje...Analizę sortowania przez scalanie przeprowadzasz ?
- 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
Sortowanie przez scalanie ma takie równanie rekurencyjne
Średni przypadek sortowania szybkiego też ma podobną rekurencję
Średni przypadek sortowania szybkiego też ma podobną rekurencję
- arek1357
- Użytkownik
- Posty: 5740
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 130 razy
- Pomógł: 525 razy
Rekurencje - metoda iteracyjna
O i widzisz pierwsze słyszę coś takiego.
to równanie Poszukującej było określone na dziedzinie będącej potęgami dwójki ja po prostu na beszczelnego dziedzinę rozszerzyłem na wszystkie...
Teraz na ten temat poczytałem to masz rację , ja osobiście nie znałem tego algorytmu , ja po prostu tu i tam dokonałem radosnej twórczości.
to równanie Poszukującej było określone na dziedzinie będącej potęgami dwójki ja po prostu na beszczelnego dziedzinę rozszerzyłem na wszystkie...
Teraz na ten temat poczytałem to masz rację , ja osobiście nie znałem tego algorytmu , ja po prostu tu i tam dokonałem radosnej twórczości.
- 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
Nie pisałeś nigdy sortowań w jakimś języku programowania jak Pascal czy C
Dla tablic Cormen podaje łatwe do przepisania pseudokody
(Algorithms unlocked, Introduction to Algorithms)
Sortowanie przez scalanie jest dobrym wyborem dla list albo plików
natomiast dla tablic tylko wtedy gdy zależy nam na szybkim algorytmie zachowującym
oryginalną kolejność powtarzających się kluczy
Jeżeli nie zależy nam na kolejności powtarzających się kluczy to dla tablic lepszym wyborem będzie sortowanie stogowe ze względu na to że działa w miejscu a standardowa wersja sortowania przez scalanie wymaga dodatkowej pamięci
I am not crazy about quicksort because it may slow down
Dla tablic Cormen podaje łatwe do przepisania pseudokody
(Algorithms unlocked, Introduction to Algorithms)
Sortowanie przez scalanie jest dobrym wyborem dla list albo plików
natomiast dla tablic tylko wtedy gdy zależy nam na szybkim algorytmie zachowującym
oryginalną kolejność powtarzających się kluczy
Jeżeli nie zależy nam na kolejności powtarzających się kluczy to dla tablic lepszym wyborem będzie sortowanie stogowe ze względu na to że działa w miejscu a standardowa wersja sortowania przez scalanie wymaga dodatkowej pamięci
I am not crazy about quicksort because it may slow down
- 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
arek1357, co powiesz na takie równanie rekurencyjne
\(\displaystyle{ T\left( n\right) =\begin{cases} 1 \qquad n=1\\ T\left( \frac{n}{k} \right)+T\left(n- \frac{n}{k} \right) + n \qquad n>1 \end{cases}}\)
\(\displaystyle{ k\in\left(1,n\right\rangle}\)
\(\displaystyle{ T\left( n\right) =\begin{cases} 1 \qquad n=1\\ T\left( \frac{n}{k} \right)+T\left(n- \frac{n}{k} \right) + n \qquad n>1 \end{cases}}\)
\(\displaystyle{ k\in\left(1,n\right\rangle}\)
Ostatnio zmieniony 27 gru 2016, o 13:18 przez Mariusz M, łącznie zmieniany 1 raz.