szukanie zaawansowane
 [ Posty: 4 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 1 lis 2016, o 22:15 
Użytkownik

Posty: 13
Lokalizacja: Poznań
Witam. W jaki sposób można sprawdzić, czy \log^{73}_2 n = O(\sqrt{n}) ?
Góra
Mężczyzna Offline
PostNapisane: 1 lis 2016, o 22:37 
Użytkownik

Posty: 12615
Mamy \lim_{n \to  \infty } \frac{\log_2^{73}n}{\sqrt{n}}=0, więc dla dostatecznie dużych n zachodzi np. nierówność \frac{\log_2^{73}n}{\sqrt{n}} \le 1, tj.
\log_2^{73}n \le \sqrt{n} dla dostatecznie dużych n. Zatem \log^{73}_2 n = O(\sqrt{n})
Góra
Mężczyzna Offline
PostNapisane: 1 lis 2016, o 22:45 
Użytkownik

Posty: 13
Lokalizacja: Poznań
A w jaki sposób można dojść do tego, że \lim_{n \to \infty } \frac{\log_2^{73}n}{\sqrt{n}}=0?
Góra
Mężczyzna Offline
PostNapisane: 1 lis 2016, o 23:10 
Użytkownik

Posty: 12615
Dla dostatecznie dużych n \in \NN mamy np.
\log_2 n \le n^{ \frac{1}{292} } (ten wykładnik jest z kapelusza wzięty).
Uzasadnienie:
równoważnie mamy, z uwagi na to, że funkcja wykładnicza o podstawie większej od 1 jest rosnąca, nierówność
n \le 2^{n^{\frac{1}{292}}} i dalej

\frac{n}{2^{n^{\frac{1}{292}}}} \le 1. A to dla dostatecznie dużych n jest prawdą, gdyż \lim_{n \to  \infty }\frac{n}{2^{n^{\frac{1}{292}}}}=0
W celu wyliczenia tej ostatniej wystarczy rozważyć granicę funkcji
\lim_{t \to  \infty } \frac{t^{292}}{2^t}=0 - to ostatnie można uzyskać np. 292 razy stosując regułę de l'Hospitala.
Skoro tak to z definicji Heinego granicy niewłaściwej funkcji wynika, że dla ciągu a_n=n^{ \frac{1}{292} } mamy \lim_{n \to  \infty } \frac{f(a_n)}{g(a_n)}=0 (f(t)=t^{292}, g(t)=2^t).

Wracając do dowodu pożądanej własności,
skoro \log_2 n \le n^{ \frac{1}{292} }, to \log^{73}_2 n \le n^{ \frac{73}{292} }=\sqrt[4]{n} i
0 \le  \frac{\log^{73}_2 n}{\sqrt{n}} \le  \frac{1}{\sqrt[4]{n}}
dla dostatecznie dużych n.

-- 1 lis 2016, o 22:16 --

Sorry że tak brzydko, ale nic lepszego nie przychodzi mi do głowy. Bez de l'Hospitala można jakoś uzasadnić, że
\lim_{t \to  \infty  } \frac{t^{292}}{2^t}=0, ale nie pamiętam jak.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 4 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Ile jest dzielnikow liczby  Anonymous  6
 ile jest liczb 2cyfr/3cyfr, 5cyfr o pocz 12, bez cyfr 4 i 5?  Anonymous  1
 permutacje/ile jest sposobow ustawien/ -prosba o sprawdzenie  alamakota  3
 Notacja  pietia  4
 ile jest liczb trzycyfrowych, mniejszych od 555  Anonymous  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl