Matematyka.pl

Treść zadania:

Znajdź najmniejsze \(\displaystyle{ k\in\mathbb{N}}\) dla którego \(\displaystyle{ f(n)=O(n^{k})}\):
\(\displaystyle{ f(n)=\sqrt{ n^{4}+n^{2} }}\)
Odpowiedź uzasadnij.

Moje rozwiązanie:

\(\displaystyle{ f(n)=\sqrt{ n^{4}+n^{2} }}\)
ponieważ \(\displaystyle{ n^{2} < n^{4}}\) dla \(\displaystyle{ n\in\mathbb{N}}\)

mamy \(\displaystyle{ \sqrt{n^{4}+n^{2}} < \sqrt{n^{4}+n^{4}}}\)

czyli \(\displaystyle{ g(n)=\sqrt{n^{4}+n^{4}}=\sqrt{2 \cdot n^{4}}= \sqrt{2} \cdot \sqrt{n^{4}}=\sqrt{2} \cdot n^{2}}\)

zatem \(\displaystyle{ g(n)=O(n^{2})}\), bo \(\displaystyle{ \exists_{C>0}g(n) qslant Cn^{2}}\), gdzie \(\displaystyle{ C= \sqrt{2}}\)

ponieważ \(\displaystyle{ \forall_{n\in\mathbb{N}}( f(n)}\)

potrzebne jeszcze funkcja ograniczająca z dołu czyli np. \(\displaystyle{ \sqrt{n^{4}}< \sqrt{n^{4}+n^{2}}}\)i dalej tak samo jak zrobiłeś wcześniej. Zauważ, że jeśli byłoby tylko te twoje górne przybliżenie to mógłbyś wykazać dowolną asymptotę czyli straszna nieprawdę. Jeżeli chcesz korzystać z takiej metody musisz miec zawsze z dołu i z góry funkcje tego samego typu aby móc wyciagnąć sensowny wniosek.

kadiii pisze:potrzebne jeszcze funkcja ograniczająca z dołu czyli np. \(\displaystyle{ \sqrt{n^{4}}< \sqrt{n^{4}+n^{2}}}\)i dalej tak samo jak zrobiłeś wcześniej. Zauważ, że jeśli byłoby tylko te twoje górne przybliżenie to mógłbyś wykazać dowolną asymptotę czyli straszna nieprawdę. Jeżeli chcesz korzystać z takiej metody musisz miec zawsze z dołu i z góry funkcje tego samego typu aby móc wyciagnąć sensowny wniosek.

Masz rację, natomiast na zajęciach - bo to zadanie ze studiów - sprawdzaliśmy tylko górne ograniczenia, zatem wystarczy mi (do zaliczenia) to.

Skoro jest poprawnie, to cieszę się.

Jeżeli jesteś pewien, że tak cie uczyli to ok. Dla mnie to jednak trochę dziwne, w rozwiązaniu korzysta się z tego, że z góry oszacowujesz wynik i tak dobierasz funkcję, zapis powinien być według mnie więc pełny. Równie dobrze mógłbyś napisać odrazu wynik, bo przecież go widać - skoro jednak chce sie coś udowodnić to trzeba to robić dobrze. Z tego rozumowania można jedynie wywnioskowość, że jest to \(\displaystyle{ O(n^2) O(n) O(1)}\) i nic wiecej.