Czy

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 Θ ( n ), a g jest lepiej niż n o dużej n ... A ponieważ g ∈ O ( n ) i g ∉ Θ ( n ) , a następnie O ( n ) ∉ Θ ( n $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..

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

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

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 Θ ( n ) są również elementami zestawu O ( n ) .$x \wedge y \implies x$$\Theta(n)$$O(n)$