Inne, zadanie nr 5651

Autor	Zadanie / 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: 8070	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