Równanie rekurencyjne - algorytmy

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Opolos
Użytkownik
Użytkownik
Posty: 1
Rejestracja: 27 sty 2020, o 05:12
Płeć: Mężczyzna
wiek: 19

Równanie rekurencyjne - algorytmy

Post autor: Opolos »

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?
Ostatnio zmieniony 27 sty 2020, o 08:54 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Awatar użytkownika
Janusz Tracz
Użytkownik
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

Post autor: Janusz Tracz »

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 }\)
Awatar użytkownika
arek1357
Użytkownik
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

Post autor: arek1357 »

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ąć...
ODPOWIEDZ