\(\displaystyle{ T(n)=4T\left( \frac{n}{2} \right) +n^2\lg n}\)
co sie robi w takich sytuacjach?? no bo twierdzenie o rekurencji uniwersalnej nie dziala w tym pyrzypadku
[Rekurencja] Trudna rekurencja
trudna rekurencja
//Edycja, skoro nie działa to poczekaj spróbuje to ogarnąć.
Działa, mi wyszło \(\displaystyle{ T(n)=\Theta (n^{2}lg^{2}n)}\)
no chyba, że się walnąłem, ale nie jest taka trudna.
Działa, mi wyszło \(\displaystyle{ T(n)=\Theta (n^{2}lg^{2}n)}\)
no chyba, że się walnąłem, ale nie jest taka trudna.
Ostatnio zmieniony 23 sie 2012, o 11:35 przez dexter90, łącznie zmieniany 1 raz.
-
kriegor
- Użytkownik
- Posty: 330
- Rejestracja: 21 sty 2012, o 20:51
- Płeć: Mężczyzna
- Lokalizacja: ut
- Podziękował: 182 razy
- Pomógł: 1 raz
trudna rekurencja
echh
\(\displaystyle{ a=4,b=2,n^{\log_b a}=n^2}\)
no i teraz korzystam z tego ... symptotyka (tam literowki sa brakuje gdzieniegdzie epsilona)
no to jedyny przypadek pod ktory to podpada to bylby trzeci tzn \(\displaystyle{ f(n)\in \Omega(n^2)}\) ale niestety nie zachodzi \(\displaystyle{ f(n)\in \Omega(n^{2+\epsilon})}\) dla zadnego \(\displaystyle{ \epsilon}\) wiec nie ma jak jej zastosowac
\(\displaystyle{ a=4,b=2,n^{\log_b a}=n^2}\)
no i teraz korzystam z tego ... symptotyka (tam literowki sa brakuje gdzieniegdzie epsilona)
no to jedyny przypadek pod ktory to podpada to bylby trzeci tzn \(\displaystyle{ f(n)\in \Omega(n^2)}\) ale niestety nie zachodzi \(\displaystyle{ f(n)\in \Omega(n^{2+\epsilon})}\) dla zadnego \(\displaystyle{ \epsilon}\) wiec nie ma jak jej zastosowac
-
kriegor
- Użytkownik
- Posty: 330
- Rejestracja: 21 sty 2012, o 20:51
- Płeć: Mężczyzna
- Lokalizacja: ut
- Podziękował: 182 razy
- Pomógł: 1 raz
trudna rekurencja
to ona naprawde jest uniwersalna szkoda ze nie znalem jej w tej ogolnej formie
to nie wyobrazam sobie przykladu ktory by z niej nie poszedl, dzieki
to nie wyobrazam sobie przykladu ktory by z niej nie poszedl, dzieki
-
norwimaj
- Użytkownik
- Posty: 5101
- Rejestracja: 11 mar 2011, o 16:31
- Płeć: Mężczyzna
- Lokalizacja: 52°16'37''N 20°52'45''E
- Podziękował: 4 razy
- Pomógł: 1001 razy
trudna rekurencja
Oczywiście nikt normalny nie będzie pamiętał założeń i tez owego twierdzenia, więc jego zastosowanie w sytuacji egzaminu jest ograniczone. Za to nie jest problemem rozpisanie sobie tej rekurencji i zobaczenie, o co chodzi.
\(\displaystyle{ T(n)=n^2\log n + 4T\left( \frac{n}{2} \right) = n^2\log n +n^2\log\frac{n}2 + 16T\left( \frac{n}4 \right) =\\\\=n^2\log n +n^2\log\frac{n}2 + n^2\log\frac{n}4+ 2^6 T\left( \frac{n}{2^3} \right)=\\\\
=n^2\log n +n^2\log\frac{n}2 + n^2\log\frac{n}4+\ldots+n^2\log\frac{n}{2^{\log_2\lceil n+1\rceil}},}\)
i teraz \(\displaystyle{ n^2}\) wyłączasz przed nawias. W praktycznej sytuacji i tak będziesz miał
\(\displaystyle{ T(n)=4T\left(\left\lceil \frac{n}{2} \right\rceil\right) +n^2\log n}\),
co nieco zmienia powyższe przekształcenia.
\(\displaystyle{ T(n)=n^2\log n + 4T\left( \frac{n}{2} \right) = n^2\log n +n^2\log\frac{n}2 + 16T\left( \frac{n}4 \right) =\\\\=n^2\log n +n^2\log\frac{n}2 + n^2\log\frac{n}4+ 2^6 T\left( \frac{n}{2^3} \right)=\\\\
=n^2\log n +n^2\log\frac{n}2 + n^2\log\frac{n}4+\ldots+n^2\log\frac{n}{2^{\log_2\lceil n+1\rceil}},}\)
i teraz \(\displaystyle{ n^2}\) wyłączasz przed nawias. W praktycznej sytuacji i tak będziesz miał
\(\displaystyle{ T(n)=4T\left(\left\lceil \frac{n}{2} \right\rceil\right) +n^2\log n}\),
co nieco zmienia powyższe przekształcenia.
trudna rekurencja
To twoje zdanie, wiele zależy od wykładowcy. Jeżeli jest złośliwy ( takiego też miałem ) na egzaminie wymagał Master Theorem. W sumie po zrobieniu kilkunastu przykładów to już raczej założenia z rękawa lecą.Oczywiście nikt normalny nie będzie pamiętał założeń i tez owego twierdzenia