[Algorytmy] Oszacowanie górne

nwnuinr
Użytkownik
Użytkownik
Posty: 375
Rejestracja: 12 mar 2008, o 11:39
Płeć: Mężczyzna
Lokalizacja: z Polski
Podziękował: 245 razy
Pomógł: 2 razy

[Algorytmy] Oszacowanie górne

Post autor: nwnuinr » 18 paź 2011, o 12:02

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.
Ostatnio zmieniony 18 paź 2011, o 14:39 przez Afish, łącznie zmieniany 1 raz.
Powód: Otagowanie tematu.

Awatar użytkownika
paladin
Użytkownik
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

Post autor: paladin » 18 paź 2011, o 22:48

nwnuinr pisze:Cześć

(...)

\(\displaystyle{ T(m^{2})=2T(m)+1 \\ S(m)=T(m^{2}) \\ S(m)=2S(m)+1= \ldots}\)
Obawiam się, że w tym miejscu źle wstawiłeś.
Rozwiązanie tej rekursji jest inne. Wstaw \(\displaystyle{ n = 2^k}\).

ODPOWIEDZ