[Teoria złożoności] Rekurencja uniwersalna
: 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?
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?