Rekurencje - metoda iteracyjna

Poszukujaca · Post autor: **Poszukujaca** » 8 gru 2016, o 23:24

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})}\)

a4karo · Post autor: **a4karo** » 8 gru 2016, o 23:25

Wzorek jest do luftu. Potrafisz powiedzieć ile to jest \(\displaystyle{ T(3)}\) ?

arek1357 · Post autor: **arek1357** » 8 gru 2016, o 23:27

Ależ fajny wzorek:

Kliknij tu:

https://www.matematyka.pl/413512.htm

Poszukujaca · Post autor: **Poszukujaca** » 8 gru 2016, o 23:44

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?

arek1357 · Post autor: **arek1357** » 8 gru 2016, o 23:46

Pobaw się nim tak jak ja i go rozciąg sobie

Poszukujaca · Post autor: **Poszukujaca** » 8 gru 2016, o 23:49

Dobrze, pobawię się

Ale czy można stwierdzić, że nie da się przeprowadzić tutaj sensownej iteracji, która doprowadzi do rozwiązania?

arek1357 · Post autor: **arek1357** » 8 gru 2016, o 23:54

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...

Mariusz M · Post autor: **Mariusz M** » 26 gru 2016, o 01:15

Analizę sortowania przez scalanie przeprowadzasz ?

arek1357 · Post autor: **arek1357** » 26 gru 2016, o 15:30

Analizę sortowania przez scalanie przeprowadzasz ?

A teraz proszę przetłumacz mi to na nasze, ja człowiek bardzo prosto myślący nie dla mnie takie indygacje...

Mariusz M · Post autor: **Mariusz M** » 26 gru 2016, o 17:48

Sortowanie przez scalanie ma takie równanie rekurencyjne
Średni przypadek sortowania szybkiego też ma podobną rekurencję

arek1357 · Post autor: **arek1357** » 26 gru 2016, o 18:02

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.

Mariusz M · Post autor: **Mariusz M** » 26 gru 2016, o 22:29

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

arek1357 · Post autor: **arek1357** » 27 gru 2016, o 04:17

No jasne pisałem za pomocą sortowania bąbelkowego w C++

Mariusz M · Post autor: **Mariusz M** » 27 gru 2016, o 13:12

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}\)

arek1357 · Post autor: **arek1357** » 27 gru 2016, o 13:17

Hmmm ciekawe ale chyba tam w drugim brakuje znaku =