Cześć, nie mogę sobie poradzić z uzasadnieniem (bo wiadomo, że równość jest prawdziwa, to znaczy ciąg po lewej nie rośnie szybciej niż pierwiastek z n):
Sprawdź, czy podana równość jest prawdziwa:
\(\displaystyle{ (log_{2}n)^{73}=O( \sqrt{n})}\)
Robię tak:
\(\displaystyle{ (log_{2}n)^{73} \le C \cdot \sqrt{n}}\)
\(\displaystyle{ (log_{2}n)^{146} \le C_{1} \cdot n}\)
wprowadzam: \(\displaystyle{ y = log_{2}n}\)
oraz: \(\displaystyle{ n = 2^{y}}\)
teraz:
\(\displaystyle{ y^{146} \le C_{1} \cdot 2^{y}}\)
Ostatnia linijka się zgadza dla dostatecznie dużych y, ale można to wyznaczyć?
Szacowanie ciągu
- JakimPL
- Użytkownik
- Posty: 2401
- Rejestracja: 25 mar 2010, o 12:15
- Płeć: Mężczyzna
- Lokalizacja: Katowice
- Podziękował: 43 razy
- Pomógł: 459 razy
Szacowanie ciągu
Wynika to stąd, iż dla dowolnego \(\displaystyle{ k\in\mathbb{R}}\) i \(\displaystyle{ a>1}\):
\(\displaystyle{ \frac{y^k}{a^y}\to 0}\)
Wystarczy wyznaczyć odpowiednią granicę. W Twoim przykładzie:
\(\displaystyle{ \frac{\log^{73}_{2}n}{\sqrt{n}} \to 0}\)
\(\displaystyle{ \log^{73}_{2}n - \sqrt{n} \to -\infty}\)
\(\displaystyle{ \frac{y^k}{a^y}\to 0}\)
Wystarczy wyznaczyć odpowiednią granicę. W Twoim przykładzie:
\(\displaystyle{ \frac{\log^{73}_{2}n}{\sqrt{n}} \to 0}\)
\(\displaystyle{ \log^{73}_{2}n - \sqrt{n} \to -\infty}\)
-
- Użytkownik
- Posty: 3
- Rejestracja: 4 kwie 2013, o 12:36
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 1 raz
Szacowanie ciągu
Wiem już, jak to ma być. Patrząc na ostatnią nierówność:
\(\displaystyle{ y^{146} \le 2^{y}}\)
można wziąć logarytm z tego:
\(\displaystyle{ log _{2} (y^{146}) \le log _{2} (2^{y})}\)
\(\displaystyle{ 146 \cdot log _{2} (y) \le y}\)
Na pewno musi też zajść nierówność:
\(\displaystyle{ 146 \cdot \sqrt{y} \le y}\)
Czyli:
\(\displaystyle{ y \ge 146^{2}}\)
Czyli:
\(\displaystyle{ n \ge 2^{146^{2}}}\)
Dobrze myślę? Czyli odpowiedź będzie, że dla dostatecznie dużych n \(\displaystyle{ (log_{2}n)^{73}}\) rośnie wolniej niż \(\displaystyle{ \sqrt{n}}\).
\(\displaystyle{ y^{146} \le 2^{y}}\)
można wziąć logarytm z tego:
\(\displaystyle{ log _{2} (y^{146}) \le log _{2} (2^{y})}\)
\(\displaystyle{ 146 \cdot log _{2} (y) \le y}\)
Na pewno musi też zajść nierówność:
\(\displaystyle{ 146 \cdot \sqrt{y} \le y}\)
Czyli:
\(\displaystyle{ y \ge 146^{2}}\)
Czyli:
\(\displaystyle{ n \ge 2^{146^{2}}}\)
Dobrze myślę? Czyli odpowiedź będzie, że dla dostatecznie dużych n \(\displaystyle{ (log_{2}n)^{73}}\) rośnie wolniej niż \(\displaystyle{ \sqrt{n}}\).
- JakimPL
- Użytkownik
- Posty: 2401
- Rejestracja: 25 mar 2010, o 12:15
- Płeć: Mężczyzna
- Lokalizacja: Katowice
- Podziękował: 43 razy
- Pomógł: 459 razy
Szacowanie ciągu
Wniosek masz dobry, ale nie wiem, na ile "czujesz", że tak musi być, jak napisałeś. Wypadałoby to rozumowanie uporządkować i sformalizować (wykorzystując definicję notacji \(\displaystyle{ O}\)). Nie do końca rozumiem przejścia z logarytmu do pierwiastka.
Musisz sobie uświadomić, jaki asymptotycznie charakter ma logarytm, funkcja wielomianowa, a jaki charakter ma funkcja wykładnicza. Wtedy ten wyliczony wniosek będzie oczywisty.
Musisz sobie uświadomić, jaki asymptotycznie charakter ma logarytm, funkcja wielomianowa, a jaki charakter ma funkcja wykładnicza. Wtedy ten wyliczony wniosek będzie oczywisty.
-
- Użytkownik
- Posty: 3
- Rejestracja: 4 kwie 2013, o 12:36
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 1 raz
Szacowanie ciągu
Dzięki za odpowiedź. Przejście z logarytmu na pierwiastek podpatrzyłem w innym przykładzie. Pozwala dalej poprowadzić rozumowanie, chociaż oczywiście moje oszacowanie jest przez to mniej dokładne.
Temat jest fajny i faktycznie wymaga poznania charakteru tych funkcji. Pozdrawiam:)
Temat jest fajny i faktycznie wymaga poznania charakteru tych funkcji. Pozdrawiam:)
- JakimPL
- Użytkownik
- Posty: 2401
- Rejestracja: 25 mar 2010, o 12:15
- Płeć: Mężczyzna
- Lokalizacja: Katowice
- Podziękował: 43 razy
- Pomógł: 459 razy
Szacowanie ciągu
W wypadku notacji "duże O", łatwo korzysta się z granic, dokładniej:
\(\displaystyle{ \lim_{x \to \infty} \left|\frac{f(x)}{g(x)}\right| < \infty \Rightarrow f(x) \in O(g(x))}\)
To jest warunek wystarczający i "omija" liczenie na piechotę.
\(\displaystyle{ \lim_{x \to \infty} \left|\frac{f(x)}{g(x)}\right| < \infty \Rightarrow f(x) \in O(g(x))}\)
To jest warunek wystarczający i "omija" liczenie na piechotę.