Cześć
mam takie zadanko: Wyznacz asymptotyczne oszacowanie górne dla rekurencji \(\displaystyle{ T(n)=2T(\sqrt{n})+1}\)
No i ja to rozwiązałem w taki sposób, ale nie jestem pewien czy jest ok.
(Gdyby ktoś potrzebował definicji na oszacowanie górne):
\(\displaystyle{ f(n)=O(g(n)) \Rightarrow \exists _{c>0,n_{0}>0} \forall _{n \ge n_{0}} 0 \le f(n) \le c \cdot g(n)}\)
\(\displaystyle{ m=\sqrt{n} \\ n=m^{2} \\ T(m^{2})=2T(m)+1 \\ S(m)=T(m^{2}) \\ S(m)=2S(m)+1=O(2^{m+1}-1)=O(2^{m})=O(2^{\sqrt{n}})}\)
Pozdrawiam i dzięki z góry za pomoc.
[Algorytmy] Oszacowanie górne
- paladin
- Użytkownik
- Posty: 148
- Rejestracja: 24 sty 2005, o 22:15
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Pomógł: 19 razy
[Algorytmy] Oszacowanie górne
Obawiam się, że w tym miejscu źle wstawiłeś.nwnuinr pisze:Cześć
(...)
\(\displaystyle{ T(m^{2})=2T(m)+1 \\ S(m)=T(m^{2}) \\ S(m)=2S(m)+1= \ldots}\)
Rozwiązanie tej rekursji jest inne. Wstaw \(\displaystyle{ n = 2^k}\).