Witam.
To mój pierwszy post na forum, proszę o wyrozumiałość .
Mam takie zadanie:
Znajdź najmniejszą liczbę \(\displaystyle{ k}\) taką, że \(\displaystyle{ f(n) = O( n^{k} )}\) :
a) \(\displaystyle{ f(n) = 13 n^{2} + 4n - 73}\)
To najłatwiejszy przykład, jeżeli ktoś mógłby mi pokazać jak rozwiązać takie zadanie krok po kroku, postaram się resztę zrobić sam.
Pozdrawiam.
Znajdź najmniejszą liczbę
Znajdź najmniejszą liczbę
Ostatnio zmieniony 6 cze 2013, o 19:12 przez Qń, łącznie zmieniany 1 raz.
Powód: Całe wyrażenia matematyczne umieszczaj w tagach[latex] [/latex]
Powód: Całe wyrażenia matematyczne umieszczaj w tagach
Znajdź najmniejszą liczbę
Symbol o którym mówisz jest używany do opisu asymptotycznego zachowania jednej funkcji wobec drugiej... Niestety nie wiem za bardzo jak ma się to do zadania i jak tego użyć.
-
Qń
- Użytkownik
- Posty: 9833
- Rejestracja: 18 gru 2007, o 03:54
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 90 razy
- Pomógł: 2632 razy
Znajdź najmniejszą liczbę
Z definicji \(\displaystyle{ f(n)= O(n^k)}\) wtedy i tylko wtedy gdy istnieje stała \(\displaystyle{ C>0}\) taka, że dla dostatecznie dużych \(\displaystyle{ n}\) zachodzi:
\(\displaystyle{ f(n) \le C \cdot n^k}\)
Zastanów się - dla jakich \(\displaystyle{ k}\) zachodzi (od pewnego miejsca) dla pewnego dodatniego \(\displaystyle{ C>0}\) nierówność:
\(\displaystyle{ 13n^2+4n-73 \le C \cdot n^k}\)
?
Czy \(\displaystyle{ k=1}\) będzie dobre?
Q.
\(\displaystyle{ f(n) \le C \cdot n^k}\)
Zastanów się - dla jakich \(\displaystyle{ k}\) zachodzi (od pewnego miejsca) dla pewnego dodatniego \(\displaystyle{ C>0}\) nierówność:
\(\displaystyle{ 13n^2+4n-73 \le C \cdot n^k}\)
?
Czy \(\displaystyle{ k=1}\) będzie dobre?
Q.