[Teoria złożoności] Rekurencja uniwersalna

muoda92
Użytkownik
Użytkownik
Posty: 17
Rejestracja: 11 maja 2012, o 23:59
Płeć: Kobieta
Podziękował: 1 raz

[Teoria złożoności] Rekurencja uniwersalna

Post autor: muoda92 » 29 cze 2017, o 15:52

Cześć
Potrzebuję pomocy przy rozwiązaniu poniższego przykładu:
\(\displaystyle{ T \left( 1 \right) =\mbox{const}, T \left( n \right) =3T\left(\frac{n}{3}\right)+ \log n}\)
Wiadomo, że \(\displaystyle{ a=3, b=3, f \left( n \right) =\log n}\)
no i \(\displaystyle{ n^{\log _b a} = n^{\log _3 3}=n}\).
wiadomo, że \(\displaystyle{ n}\) jest większe od \(\displaystyle{ \log n}\) i tutaj mam problem, bo z tego co czytałam nie powinnam skorzystać tutaj z Twierdzenia o rekurencji uniwersalnej bo \(\displaystyle{ n}\) nie jest wielomianowo większe od logarytmu.
W tym przypadku, aby to uzasadnić powinnam chyba rozważyć współczynnik
\(\displaystyle{ \frac{f \left( n \right) }{\log _b a} = \frac{\log n}{n} > \frac{1}{n^{\epsilon}}}\).

Jaki wniosek powinnam z tego wyciągnąć i dlaczego?
Ostatnio zmieniony 29 cze 2017, o 19:31 przez Afish, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.

ODPOWIEDZ