Matematyka.pl

\(\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

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

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

Case 2 i wyjdzie jak pisałem.

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

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.

Oczywiście nikt normalny nie będzie pamiętał założeń i tez owego twierdzenia

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