Matematyka.pl

Szukając w Internecie definicji notacji dużego O bardzo się rozczarowałem i jedyne co znalazłem, to ten fragment z wikipedii:



Jest tam przedstawiona defincja:

Mówimy, że \(\displaystyle{ f}\) jest co najwyżej rzędu \(\displaystyle{ g,}\) gdy istnieją takie stałe \(\displaystyle{ {\displaystyle n_{0}>0,}}\) oraz \(\displaystyle{ {\displaystyle c>0,} }\) że:

\(\displaystyle{ {\displaystyle \forall n\geqslant n_{0}:f(n)\leqslant c\cdot g(n)}}\)

Zapis: \(\displaystyle{ {\displaystyle f(n)\in \mathrm {O} (g(n))}}\)

Z drugiej strony w podręczniku znalazłem następujące twierdzenie:

Jeżeli \(\displaystyle{ A }\)jest liczbą naturalną, a funkcja \(\displaystyle{ f(t) > 0}\) jest monotoniczna w przedziale domkniętym \(\displaystyle{ [A, x]}\), to

\(\displaystyle{ \sum_{A \le n \le x} f(n) = \int_{A}^{x} f(t) \mbox{dt} + O(f(A)) + O(f(x))}\)

I nie wiem jak to ma się do siebie. W Wikipedii mam relację należenia, w podręczniku relację równości...
Jak należy rozumieć \(\displaystyle{ O(\cdot)}\) z podręcznika?

Dziękuję, a znasz (lub jesteś w stanie ad hoc wymyślić) jakieś zadania, które pomogłyby zrozumieć w praktyce to zagadnienie? Przepraszam jeśli proszę o zbyt dużo, zawsze mam problem z proszeniem o pomoc, nie wiem gdzie jest granica.

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.

• Powiemy, że \(\displaystyle{ f(n)\in \mathrm {O} (g(n))}\), gdy
  \(\displaystyle{ \left( \exists N>0\right) \left( \exists c>0\right) \left( \forall n\geqslant N\right) f(n)\leqslant c\cdot g(n).}\)

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

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


oraz czy

Na angielskiej Wiki też jest kilka ciekawych twierdzeń które możesz udowodnić. Przykładowo




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


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.