Notacja asymptotyczna

[drooone]

Witam
Mam takie proste zadanie, znam wynik(True) ale prosilbym o jakies proste wyjasnienie
jak tego typu zadania sie rozwiazuje.
Zad.
Czy istnieje funkcja \(\displaystyle{ f(n):N \rightarrow R}\) taka ze jezeli
\(\displaystyle{ f(n)=\Omega \left (n^{ \sqrt{2}\right)}\) to \(\displaystyle{ f(n) = \Theta (n)+ \Omega \left (n^{ \sqrt{2}\right)+ \Theta \left(n^{ \frac{3}{2}\right)}\)

Odp. Musze udzielic prawda falsz
Z gory dzieki za pomoc

[royas]

Co oznacza \(\displaystyle{ +}\) w tym kontekście?

[norwimaj]

To wygląda na zadanie z logiki.

Czy istnieje funkcja \(\displaystyle{ f(n):N \rightarrow R}\) taka ze jezeli
\(\displaystyle{ f(n)=\Omega \left (n^{ \sqrt{2}\right)}\) to (...)

Wystarczy wziąć funkcję, która nie jest \(\displaystyle{ \Omega \left (n^{ \sqrt{2}\right)}\).

Co oznacza \(\displaystyle{ +}\) w tym kontekście?

Zapewne dodawanie.

[royas]

Ale dodawanie czego? Chyba zbiorów. Wtedy dowolna funkcja \(\displaystyle{ f(n):N \rightarrow R}\) pasuje.

[norwimaj]

Ale dodawanie czego? Chyba zbiorów.

Tak. Konkretnie rodzin funkcji, przy czym chodzi o dodawanie arytmetyczne, nie mnogościowe.

Wtedy dowolna funkcja \(\displaystyle{ f(n):N \rightarrow R}\) pasuje.

Tak. Do tego zadania pasuje dowolna funkcja.

[royas]

Co jest wynikiem takiego dodawana?
Aha rozumiem chyba. Każdy składnik oznacza dodanie jakiejś funkcji z danej rodziny.

[norwimaj]

\(\displaystyle{ \Theta (n)+ \Omega \left (n^{ \sqrt{2}\right)+ \Theta \left(n^{ \frac{3}{2}\right)}\) to jest dokładnie to samo, co \(\displaystyle{ \Omega\left(n^{ \frac{3}{2}\right)}\), ale trzeba wiedzieć, że symbol \(\displaystyle{ =}\) tu nie oznacza naprawdę równości. Zapis

\(\displaystyle{ n^2+n=\Theta(n^2)}\)

w rzeczywistości oznacza, że funkcja \(\displaystyle{ n\mapsto n^2+n}\) należy do rodziny \(\displaystyle{ \Theta(n^2)}\), a zapis

\(\displaystyle{ O(n^2)=O(n^3)}\)

oznacza, że rodzina \(\displaystyle{ O(n^2)}\) jest zawarta w \(\displaystyle{ O(n^3)}\). Nie można tego pisać w drugą stronę, czyli nieprawdziwe są "równości"

\(\displaystyle{ \Theta(n^2)=n^2+n,}\)

\(\displaystyle{ O(n^3)=O(n^2).}\)


Już wracam do pytania. Symbol \(\displaystyle{ +}\) na zbiorach definiujemy jako

\(\displaystyle{ A+B=\{a+b:a\in A, b\in B\}.}\)

Tu \(\displaystyle{ A}\) i \(\displaystyle{ B}\) są zbiorami funkcji, więc symbol \(\displaystyle{ +}\) po prawej stronie oznacza dodawanie funkcji, zdefiniowane

\(\displaystyle{ (f+g)(n)=f(n)+g(n),}\)

gdzie \(\displaystyle{ +}\) po prawej stronie oznacza już zwykłe dodawanie liczb.

[drooone]

ok tylko jak takie zadania liczyc bo mam ich sporo

[norwimaj]

Tak jak napisałem, wystarczy wziąć funkcję, która nie jest \(\displaystyle{ \Omega \left (n^{ \sqrt{2}\right)}\), na przykład funkcję stale równą \(\displaystyle{ 1}\). Wtedy nie trzeba wnikać, co to jest \(\displaystyle{ \Theta (n)+ \Omega \left (n^{ \sqrt{2}\right)+ \Theta \left(n^{ \frac{3}{2}\right)}\).

[royas]

\(\displaystyle{ A+B=\{a+b:a\in A, b\in B\}.}\)

Dzięki. O to mi chodziło.

[drooone]

dobra to moze sprobuje z innej strony
Inny przyklad
Czy ponizsze zdanie jest prawdziwe
Dla kazdej funkcji:
\(\displaystyle{ f(n) = \Theta (n^2)+ \Omega \left (n^{ \frac{5}{2}\right)+ O \left(n^{ \sqrt{3}\right)}\)
to
\(\displaystyle{ f(n) = \Omega (loglog(n))+ \Theta \left (log^{4}(n)\right)+ O \left(n^{ \sqrt{2}\right)}\)

i jak cos takiego ugryzc

[norwimaj]

\(\displaystyle{ f(n) = \Theta (n^2)+ \Omega \left (n^{ \frac{5}{2}\right)+ O \left(n^{ \sqrt{3}\right)}\)

Czyli \(\displaystyle{ f(n)=f_1(n)+f_2(n)+f_3(n)}\), gdzie \(\displaystyle{ f_i}\) są funkcjami spełniającymi pewne warunki. Mam pewne wątpliwości, czy dopuszczamy funkcje ujemne, czyli czy \(\displaystyle{ f_3}\) może być ujemne. Jak to mieliście zdefiniowane? Czy na przykład funkcja \(\displaystyle{ -n^2}\) jest rzędu \(\displaystyle{ O(n)}\)?

W każdym razie trzeba oszacować rząd funkcji \(\displaystyle{ f}\). Funkcja \(\displaystyle{ f_1}\) jest rzędu \(\displaystyle{ \Omega(n^2)}\), funkcja \(\displaystyle{ f_2}\) rzędu \(\displaystyle{ \Omega \left (n^{ \frac{5}{2}\right)}\), więc ich suma jest rzędu \(\displaystyle{ \Omega(n^{\frac52})}\). Natomiast nie da się sumy \(\displaystyle{ f_1+f_2}\) oszacować z góry, bo funkcja \(\displaystyle{ f_2}\) może być dowolnie dużego rzędu. Jak to będzie po dodaniu \(\displaystyle{ f_3}\), to już zależy od tego, czy dopuszczamy funkcje ujemne i jak wtedy definiujemy notację \(\displaystyle{ O}\).

[drooone]

No w tym przypadku
\(\displaystyle{ n\in \mathbb{N}}\)

Czyli piszesz ze w tego typu zadaniach nalezy po prostu zbadac rzad funkcji po "lewej" i po "prawej"
a potem ?

[norwimaj]

Wiem, że \(\displaystyle{ n\in\mathbb N}\), ale nie wiem, jakie dopuszczamy \(\displaystyle{ f_3(n)}\). Tylko dodatnie, czy ujemne też. A jeśli ujemne też, to jak rozumieć notację \(\displaystyle{ O}\) dla nich?

Czy na przykład funkcja \(\displaystyle{ -n^2}\) jest rzędu \(\displaystyle{ O(n)}\)?