logowanie

matematyka » forum » studia » zadanie

Inne, zadanie nr 5651

ostatnie wiadomości  |  regulamin  |  latex

AutorZadanie / Rozwiązanie

redputron123
postów: 2
2018-01-08 22:28:32

Witam,
Mam do rozwiązania zadanie którego już od dłuższego czasu nie mogę rozwiązać.Do każdego pod punktu trzeba wybrać odpowiedz tak lub nie.

Dla danej funkcji f chcemy znaleźć najmniejsze k takie, że f(n) = O(nk).
A) Jeśli f(n) = (n^3 +3n−1)^4 to k = 81.Odpowiedz tak lub nie
B) Jeśli f(n) = (n^2 +1)^2 ·(n^3 +1) to k = 12. Odpowiedz tak lub nie
C) istnieje C > 0 takie, że n +100 < lub = Cn2 dla prawie wszystkich n. odpowiedz tak lub nie

Z góry dziękuje za pomoc



tumor
postów: 8085
2018-01-14 23:27:51

Notacja
$f(n)=O(g(n))$ oznacza, że istnieje dodatnia stała $c$ taka, że dla prawie wszystkich $n$ zachodzi
$f(n)\leq cg(n)$

Po pierwsze zgaduję (a nie lubię zgadywać), że mówimy o funkcjach $O(n^k)$, a nie $O(nk)$.

A) tak czy inaczej odpowiedź brzmi nie. Ta funkcja nie jest wcale $O(kn)$ dla żadnego $k$, natomiast jest $O(n^{12})$ (na przykład ze stałą $c=2$)

B) tak czy inaczej nie. Ta funkcja nie jest $O(nk)$ dla żadnego $k$, jest natomiast $O(n^7$) ze stałą $c=2$

C) $n+100\leq cn^2$ z każdą stałą dodatnią $c$ jest prawdą dla prawie wszystkich $n$.

strony: 1

Prawo do pisania przysługuje tylko zalogowanym użytkownikom. Zaloguj się lub zarejestruj





© 2017 Mariusz Śliwiński      o serwisie | kontakt online: 13 drukuj