Witam,
Muszę uporządkować następujące funkcje logarytmicznie od najwolniej do najszybciej rosnącej:
\(\displaystyle{ 2^\sqrt{\log n}}\)
\(\displaystyle{ n^{\log n}}\)
\(\displaystyle{ n({\log n})^3}\)
Nie wiem jednak jak zabrać się za upraszczanie tych wyrażeń. Czy ktoś ma jakiś pomysł?
Uporządkowanie funkcji logarytmicznych
-
Janusz Tracz
- Użytkownik
- Posty: 4068
- Rejestracja: 13 sie 2016, o 15:01
- Płeć: Mężczyzna
- Lokalizacja: hrubielowo
- Podziękował: 80 razy
- Pomógł: 1393 razy
Re: Uporządkowanie funkcji logarytmicznych
Powiedzmy, że jeśli \(\displaystyle{ a_n}\) będzie rosło szybciej od \(\displaystyle{ b_n}\) to oznaczymy to jako \(\displaystyle{ b_n \prec a_n }\) i będzie oznaczać to, że:
Spostrzeżenia:
\(\displaystyle{ \bullet}\) Wyrażanie \(\displaystyle{ n^{\log n}}\) rożnie najszybciej (i szybciej od dowolnego wielomianu)
\(\displaystyle{ \bullet}\) Wyrażanie \(\displaystyle{ n({\log n})^3}\) dąży wolniej od \(\displaystyle{ n^2}\) (w razie konieczności można to jeszcze lepiej oszacować) bo dla dużych \(\displaystyle{ n}\) zachodzi \(\displaystyle{ n({\log n})^3<n^2}\).
\(\displaystyle{ \bullet}\) Pytanie jak się do tego ma \(\displaystyle{ 2^\sqrt{\log n}}\) ? Na pewno \(\displaystyle{ 2^\sqrt{\log n}\prec n^{\log n}}\) więc pozostaje zastanowić się jak się ma \(\displaystyle{ 2^\sqrt{\log n}}\) do \(\displaystyle{ n({\log n})^3}\). W tym celu można policzyć granicę ich iloczynu. Albo szacować dalej. Wskazówka \(\displaystyle{ 2^\sqrt{\log n}< 10^{\log n}=n}\) więc tempo \(\displaystyle{ 2^\sqrt{\log n}}\) nie przekracza wzrostu liniowego a zachodzi \(\displaystyle{ n\prec n({\log n})^3}\).
\(\displaystyle{ \lim_{ n\to \infty } \frac{a_n}{b_n}= \infty }\)
Spostrzeżenia:
\(\displaystyle{ \bullet}\) Wyrażanie \(\displaystyle{ n^{\log n}}\) rożnie najszybciej (i szybciej od dowolnego wielomianu)
\(\displaystyle{ \bullet}\) Wyrażanie \(\displaystyle{ n({\log n})^3}\) dąży wolniej od \(\displaystyle{ n^2}\) (w razie konieczności można to jeszcze lepiej oszacować) bo dla dużych \(\displaystyle{ n}\) zachodzi \(\displaystyle{ n({\log n})^3<n^2}\).
\(\displaystyle{ \bullet}\) Pytanie jak się do tego ma \(\displaystyle{ 2^\sqrt{\log n}}\) ? Na pewno \(\displaystyle{ 2^\sqrt{\log n}\prec n^{\log n}}\) więc pozostaje zastanowić się jak się ma \(\displaystyle{ 2^\sqrt{\log n}}\) do \(\displaystyle{ n({\log n})^3}\). W tym celu można policzyć granicę ich iloczynu. Albo szacować dalej. Wskazówka \(\displaystyle{ 2^\sqrt{\log n}< 10^{\log n}=n}\) więc tempo \(\displaystyle{ 2^\sqrt{\log n}}\) nie przekracza wzrostu liniowego a zachodzi \(\displaystyle{ n\prec n({\log n})^3}\).