Która z poniższych zależności jest prawdziwa, a która fałszywa? Odpowiedź dokładnie uzasadnij (tam, gdzie jest prawdziwa należy napisać odpowiednie oszacowanie podając c, n0).
a) \(2n^2 + 3nlogn^2 + 20 = O(n^3)\)
b) \(2n^2 + 3nlogn^2 + 20 = θ(n^3)\)
c) \(\frac{1}{4} + 30n + 1 = Ω(n^2)\)
d) \(\frac{1}{4} + 30n + 1 = Ω(n^4)\)
Próbowałem to rozwiązać, poprzez obliczanie górnej oraz dolnej granicy, średnio zostalo nam to wytlumaczone na zajeciach, wiec generalnie ciezko mi sie zabrac za te zadania :/
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ć:
Re: Notacja asymptotyczna
Tutaj kliknij - jest to ładnie wyjaśnione.
Przewiń do nagłówka: Zależności algebraiczne
Przewiń do nagłówka: Zależności algebraiczne
-
panb
- Expert
- Posty: 5122
- Rejestracja: 26 kwie 2010, 22:54
- Lokalizacja: Nowiny Wielkie
- Podziękowania: 19 razy
- Otrzymane podziękowania: 2053 razy
- Płeć:
Re: Notacja asymptotyczna
Nie bardzo wiem o co ci chodzi?
Weźmy a):
\( \Lim_{n\to\infty } \begin{vmatrix} \frac{2n^2+3n\ln n^2+20}{n^3} \end{vmatrix}=0<\infty \), więc a) jest prawdziwe.
Teraz możemy myśleć o c i \(n_0\).
\(2n^2+3n\ln n^2+20=2n^2+6n\ln n+20\le 2n^2+6n^2+20=8n^2+20\)
Dla \(n\ge 5,\,\,\, 20\le n^2 \So 8n^2+20\le 8n^2+n^2=9n^2\le 9n^3\)
Czyli \( \forall _{n\ge5}2n^2+3n\ln n^2+20\le 9n^3 \So n_0=5, c=9\)
Weźmy a):
\( \Lim_{n\to\infty } \begin{vmatrix} \frac{2n^2+3n\ln n^2+20}{n^3} \end{vmatrix}=0<\infty \), więc a) jest prawdziwe.
Teraz możemy myśleć o c i \(n_0\).
\(2n^2+3n\ln n^2+20=2n^2+6n\ln n+20\le 2n^2+6n^2+20=8n^2+20\)
Dla \(n\ge 5,\,\,\, 20\le n^2 \So 8n^2+20\le 8n^2+n^2=9n^2\le 9n^3\)
Czyli \( \forall _{n\ge5}2n^2+3n\ln n^2+20\le 9n^3 \So n_0=5, c=9\)