Notacja duże O

Sigma-ciała i zbiory borelowskie. Miary, miary zewnętrze i miara Lebesgue'a. Funkcje mierzalne. Całka Lebesgue'a. Inne zagadnienia analizy rzeczywistej.
Bran
Użytkownik
Użytkownik
Posty: 421
Rejestracja: 19 lut 2019, o 19:30
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 163 razy
Pomógł: 16 razy

Notacja duże O

Post autor: Bran »

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

Kod: Zaznacz cały

https://pl.wikipedia.org/wiki/Asymptotyczne_tempo_wzrostu#Notacja_%E2%80%9Edu%C5%BCe_O%E2%80%9D


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?
Awatar użytkownika
Janusz Tracz
Użytkownik
Użytkownik
Posty: 4060
Rejestracja: 13 sie 2016, o 15:01
Płeć: Mężczyzna
Lokalizacja: hrubielowo
Podziękował: 79 razy
Pomógł: 1391 razy

Re: Notacja duże O

Post autor: Janusz Tracz »

Kod: Zaznacz cały

https://en.wikipedia.org/wiki/Big_O_notation#Infinite_asymptotics
Bran
Użytkownik
Użytkownik
Posty: 421
Rejestracja: 19 lut 2019, o 19:30
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 163 razy
Pomógł: 16 razy

Re: Notacja duże O

Post autor: Bran »

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.
Awatar użytkownika
Janusz Tracz
Użytkownik
Użytkownik
Posty: 4060
Rejestracja: 13 sie 2016, o 15:01
Płeć: Mężczyzna
Lokalizacja: hrubielowo
Podziękował: 79 razy
Pomógł: 1391 razy

Re: Notacja duże O

Post autor: Janusz Tracz »

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
\(\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.
ODPOWIEDZ