Dzień dobry,
mam problem z następującym zagadnieniem rekurencyjnym:
\(\displaystyle{ T(n) = T\left( \frac{n}{4}\right) + T\left( \frac{3n}{4} \right) + n^2 }\)
Czy da się je rozwiązać za pomocą drzew rekursji? Ewentualnie jak do tego podejść za pomocą tw. o rekurencji uniwersalnej?
Równanie rekurencyjne - algorytmy
Równanie rekurencyjne - algorytmy
Ostatnio zmieniony 27 sty 2020, o 08:54 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
- Janusz Tracz
- Użytkownik
- Posty: 4060
- Rejestracja: 13 sie 2016, o 15:01
- Płeć: Mężczyzna
- Lokalizacja: hrubielowo
- Podziękował: 79 razy
- Pomógł: 1391 razy
Re: Równanie rekurencyjne - algorytmy
Nieszczególne znam się na tych zadaniach ale zauważyłem coś co może pomóc. Postać rozwiązania można przewidywać, że będzie w formie \(\displaystyle{ an^2}\). Heurystycznie prawa strona jest od mniejszych argumentów niż \(\displaystyle{ n}\) a potem dodajemy \(\displaystyle{ n^2}\) więc może istnieją taka stała dla której będzie to własnie \(\displaystyle{ an^2}\). Po podstawianiu dostajemy warunek na stałą \(\displaystyle{ a}\).
\(\displaystyle{ an^2=a \frac{n^2}{16}+a \frac{9n^2}{16}+n^2 }\)
czyli
\(\displaystyle{ a= \frac{a}{16} + \frac{9a}{16} +1}\)
zatem \(\displaystyle{ a= \frac{8}{3} }\). Więc \(\displaystyle{ T(n)= \frac{8}{3}n^2 }\)
\(\displaystyle{ an^2=a \frac{n^2}{16}+a \frac{9n^2}{16}+n^2 }\)
czyli
\(\displaystyle{ a= \frac{a}{16} + \frac{9a}{16} +1}\)
zatem \(\displaystyle{ a= \frac{8}{3} }\). Więc \(\displaystyle{ T(n)= \frac{8}{3}n^2 }\)
- arek1357
- Użytkownik
- Posty: 5703
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 129 razy
- Pomógł: 524 razy
Re: Równanie rekurencyjne - algorytmy
nie wiaqdomo czy objąłeś wszystkie przypadki :
[Teoria złożoności] Rekurencja uniwersalna
Dodano po 8 minutach 7 sekundach:
[Algorytmy] Równanie rekurencyjne
Dodano po 2 minutach 33 sekundach:
tu masz dobrze rozpisane :
Równanie rekurencyjne
Dodano po 1 dniu 1 godzinie 57 minutach 24 sekundach:
To co się dało z tym zrobić to jest:
najpierw wzór po zamianie n:=4n:
\(\displaystyle{ T(4n)=T(n)+T(3n)+16n^2}\)
łatwo zauważyć, że:
\(\displaystyle{ T(0)=0}\)
dalej:
\(\displaystyle{ T(4)=T(1)+T(3)+16 \cdot 1^2}\)
\(\displaystyle{ T(4 \cdot 4)=T(4)+T(3 \cdot 4)+16 \cdot 16 \cdot 4^2=T(1)+T(3)+16 \cdot 1^2+T(3 \cdot 4)+16 \cdot 16 \cdot 4^2}\)
\(\displaystyle{ T(4 \cdot 16)=T(16)+T(3 \cdot 16)+16 \cdot 16 \cdot 16^2=T(1)+T(3)+T(3 \cdot 4)+16 \cdot 1^2+16 \cdot 4^2+T(3 \cdot 4^2)+16 \cdot 4^{2 \cdot 2}}\)
idąc dalej rekurencją otrzymamy:
\(\displaystyle{ T(4^{n+1})=T(4^n)+T(3 \cdot 4^n)+16 \cdot 4^{2n}}\)
lub:
\(\displaystyle{ T(4^{n+1})=T(1)+ \sum_{i=0}^{n}T(3 \cdot 4^i)+16(1^2+4^2+4^{2 \cdot 2}+...+4^{2n}) }\)
ponieważ.: \(\displaystyle{ T(0)=0}\) i kożystając ze wzoru na sumę ciągu geometrycznego otrzymamy:
\(\displaystyle{ T(4^{n+1})=T(1)+ \sum_{i=1}^{n}T(3 \cdot 4^i)+16( \frac{4^{2n+2}-1}{15}) }\)
Raczej z tego nic już bardziej trudno wycisnąć...
[Teoria złożoności] Rekurencja uniwersalna
Dodano po 8 minutach 7 sekundach:
[Algorytmy] Równanie rekurencyjne
Dodano po 2 minutach 33 sekundach:
tu masz dobrze rozpisane :
Równanie rekurencyjne
Dodano po 1 dniu 1 godzinie 57 minutach 24 sekundach:
To co się dało z tym zrobić to jest:
najpierw wzór po zamianie n:=4n:
\(\displaystyle{ T(4n)=T(n)+T(3n)+16n^2}\)
łatwo zauważyć, że:
\(\displaystyle{ T(0)=0}\)
dalej:
\(\displaystyle{ T(4)=T(1)+T(3)+16 \cdot 1^2}\)
\(\displaystyle{ T(4 \cdot 4)=T(4)+T(3 \cdot 4)+16 \cdot 16 \cdot 4^2=T(1)+T(3)+16 \cdot 1^2+T(3 \cdot 4)+16 \cdot 16 \cdot 4^2}\)
\(\displaystyle{ T(4 \cdot 16)=T(16)+T(3 \cdot 16)+16 \cdot 16 \cdot 16^2=T(1)+T(3)+T(3 \cdot 4)+16 \cdot 1^2+16 \cdot 4^2+T(3 \cdot 4^2)+16 \cdot 4^{2 \cdot 2}}\)
idąc dalej rekurencją otrzymamy:
\(\displaystyle{ T(4^{n+1})=T(4^n)+T(3 \cdot 4^n)+16 \cdot 4^{2n}}\)
lub:
\(\displaystyle{ T(4^{n+1})=T(1)+ \sum_{i=0}^{n}T(3 \cdot 4^i)+16(1^2+4^2+4^{2 \cdot 2}+...+4^{2n}) }\)
ponieważ.: \(\displaystyle{ T(0)=0}\) i kożystając ze wzoru na sumę ciągu geometrycznego otrzymamy:
\(\displaystyle{ T(4^{n+1})=T(1)+ \sum_{i=1}^{n}T(3 \cdot 4^i)+16( \frac{4^{2n+2}-1}{15}) }\)
Raczej z tego nic już bardziej trudno wycisnąć...