Okresl porzadek asymptotycznego wzrostu dla nastepujacych funkcji:
\(n^{2}\)*\(log_2(n)\)
\(n\)*\((log_2(n))^3\)
\(2^{log_2(n^2)}\)
\(n^{log_2(n)}\)
Notacja asymptotyczna
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
-
panb
- Expert
- Posty: 5122
- Rejestracja: 26 kwie 2010, 22:54
- Lokalizacja: Nowiny Wielkie
- Podziękowania: 19 razy
- Otrzymane podziękowania: 2053 razy
- Płeć:
Nie wiem czy chodzi o O-duże, czy o-małe. Zakładam, że duże.
\(n^2=O(n^2), \quad log_2n=O(n) \So n^2log_2n=O(n^3)\\ \text{ lub też }
\Lim_{n\to \infty } \frac{n^2log_2n}{n^3}= \Lim_{n\to \infty } \frac{log_2n}{n}=0< \infty \So n^2log_2n=O(n^3)\)
\(n=O(n), \quad (log_2n)^3=O(n^3) \So n(log_2n)^3=O(n^4)\\ \text{ lub też ... zrób to sam}\)
Reszta analogicznie.
Odp.:
\(n^2=O(n^2), \quad log_2n=O(n) \So n^2log_2n=O(n^3)\\ \text{ lub też }
\Lim_{n\to \infty } \frac{n^2log_2n}{n^3}= \Lim_{n\to \infty } \frac{log_2n}{n}=0< \infty \So n^2log_2n=O(n^3)\)
\(n=O(n), \quad (log_2n)^3=O(n^3) \So n(log_2n)^3=O(n^4)\\ \text{ lub też ... zrób to sam}\)
Reszta analogicznie.
Odp.:
- \(2^{\log_2n^2}=O(2^{n^2})\\
n^{\log_2n}=O(n^n)\)