Nie przychodzi mi do głowy żadne konkretne zadanie z tego tematu. Ja nie jestem fanem tej notacji praktycznie nigdy tego nie używam. Gdybym miał coś polecić aby to zrozumieć to zaczął bym od definicji i kontekstu
- Niech będą dane funkcje \(\displaystyle{ f,g}\), których dziedziną jest zbiór liczb naturalnych, natomiast przeciwdziedziną zbiór liczb rzeczywistych dodatnich.
Czyli wiemy już, że takie napisy mają sens, gdy mamy do czynienia z dodatnim ciągiem. Dalej Wikipedia podaje, że aby
\(\displaystyle{ f(n)\in \mathrm {O} (g(n))}\) wystarczy by
\(\displaystyle{ \lim _{n\to \infty }\left|{\frac {f(n)}{g(n)}}\right|<\infty}\).
Udowodnij to. Zastanów się czy zachodzi implikacja odwrotna. Zastanów się czy jest tu potrzebny ten moduł (jest na Wiki ale po co?). Potem możesz poszukać kilku konkretnych ciągów
\(\displaystyle{ f,g}\) takich, że
\(\displaystyle{ f(n)\in \mathrm {O} (g(n))}\). Możesz zastanowić się czy zachodzi implikacja
\(\displaystyle{ f(n)\in \mathrm {O} (g(n)) \ \Rightarrow \ g(n)\in O(f(n))}\)
oraz czy
\(\displaystyle{ f(n)\in \mathrm {O} (f(n)).}\)
Na angielskiej Wiki też jest kilka ciekawych twierdzeń które możesz udowodnić. Przykładowo
\(\displaystyle{ f_{1}\in O(g_{1}) \ \ \& \ \ f_{2}\in O(g_{2})\Rightarrow f_{1}f_{2}\in O(g_{1}g_{2})}\)
\(\displaystyle{ f_{1}\in O(g_{1}) \ \ \& \ \ f_{2}\in O(g_{2})\Rightarrow f_{1}+f_{2}\in O(\max{\left\{ g_{1},g_{2}\right\} })}\)
Oraz, że
\(\displaystyle{ \limsup _{n\to \infty }{\frac {\left|f(n)\right|}{g(n)}}<\infty}\) jest równoważne z
\(\displaystyle{ f(n)\in \mathrm {O} (g(n))}\). I tak dalej. Wyszukuj własność, a potem staraj się jej dowieść. Zauważy też, że można się spotkać z równymi typami zapisów
\(\displaystyle{ f(n)= \mathrm {O} (g(n)) , \qquad f(n)\in \mathrm {O} (g(n)), \qquad f= \mathrm {O} (g), \qquad f\in \mathrm {O} (g)}\)
możesz się zastanowić które są lepsze z formalnego względu od innych ale nie będę Ci tu dawał lekcji formalizmów ani tym bardziej podejmował się próby wyjaśnienia dlaczego stosuje się wszystkie cztery wersję bo nie mam odpowiednich kwalifikacji.