Czy

11

Mam więc pytanie, aby udowodnić stwierdzenie:

$O(n)\subset\Theta(n)$ ...

Nie muszę wiedzieć, jak to udowodnić, po prostu myślę, że to nie ma sensu i myślę, że powinno raczej być tak $\Theta(n)\subset O(n)$ .

Rozumiem, że $O(n)$ jest zbiorem wszystkich funkcji, które nie działają gorzej niż $n$ podczas gdy $\Theta(n)$ jest zbiorem wszystkich funkcji, które nie działają lepiej i nie gorzej niż n.

Korzystając z tego, mogę wymyślić przykład funkcji stałej, powiedzmy $g(n)=c$ . Ta funkcja z pewnością będzie elementem $O(n)$ ponieważ nie będzie gorsza niż $n$ gdy $n$ zbliży się do wystarczająco dużej liczby.

Jednakże, funkcje te same nie byłoby elementu a g jest lepiej niż o dużej ... A ponieważ i , a następnie $g$ $\Theta(n)$ $n$ $n$ $g \in O(n)$ $g \not\in \Theta(n)$ $O(n)\not\in\Theta(n)$

Czy to pytanie może być błędne? Nauczyłem się, że takie założenie jest niebezpieczne i zwykle coś przeoczyłem, po prostu nie widzę, co to może być w tym przypadku.

Jakieś pomysły ? Wielkie dzięki..

asymptotics mathematical-analysis landau-notation

— Rawb
źródło

5

Pomyśl o

. następnie

ale

. Więc „

” jest słabszym popytem, dlatego zawiera więcej funkcji ..

f = 0

$f=0$

f = O (n)

$f=O(n)$

f \neq Θ (n)

$f\not=\Theta(n)$

O (\cdot)

$O(\cdot)$

— Ran G.

5

Myślę, że masz rację, wydaje się, że to pomyłka.

— Yuval Filmus,

3

Co rozumiesz przez zapis

: podzbiór lub odpowiedni podzbiór? Radzę używać

lub

aby uniknąć nieporozumień.

\subset

$\subset$

\subseteq

$\subseteq$

⊊

$\subsetneq$

— A.Schulz,

11

Za sugestią Rafaela zamieściłem poprzedni komentarz w tę odpowiedź.

Nie jest prawdą, że . W rzeczywistości z definicji. Mamy więc . $O(f(n)) \subset \Theta(f(n))$ $\Theta(f(n)) = O(f(n)) \cap \Omega(f(n))$ $\Theta(f(n)) \subset O(f(n))$

— Patrick87
źródło

4

Pomyśl o tym w ten sposób: każda funkcja, która działa „nie gorzej niż n” i „nie lepiej niż n”, jest również funkcją, która „nie gorzej niż n”. Część „nie lepiej niż n” to tylko dodatkowe ograniczenie. Jest to proste zastosowanie reguły logicznej, która mówi: . Zgodnie z tym rozumowaniem wszystkie funkcje znajdujące się w zbiorze są również elementami zestawu . $x \wedge y \implies x$ $\Theta(n)$ $O(n)$

— saadtaame
źródło