Ist

Ich habe also diese Frage, um eine Aussage zu beweisen:

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

Ich brauche nicht zu wissen , wie es zu beweisen, dass gerade in meinem Kopf dies keinen Sinn macht , und ich denke , es sollte vielmehr sein , dass .$\Theta(n)\subset O(n)$

Mein Verständnis ist, dass die Menge aller Funktionen ist, die nicht schlechter als n sind, während Θ ( n ) die Menge aller Funktionen ist, die nicht besser und nicht schlechter als n sind.$O(n)$$n$$\Theta(n)$

Mit diesem kann ich mir das Beispiel einer konstanten Funktion vorstellen, sagen wir . Diese Funktion wird sicherlich ein Element von O ( n ) sein, da sie nicht schlechter als n ist, wenn sich n einer ausreichend großen Zahl nähert.$g(n)=c$$O(n)$$n$$n$

Allerdings ist die gleiche Funktion nicht ein Element sein Θ ( n ) als g besser macht als n für große n ... Dann , da g ∈ O ( n ) und g ∉ Θ ( n ) , dann O ( n ) ∉ Θ ( n $g$$\Theta(n)$$n$$n$$g \in O(n)$$g \not\in \Theta(n)$$O(n)\not\in\Theta(n)$

Ist die Frage vielleicht falsch? Ich habe gelernt, dass es gefährlich ist, diese Annahme zu treffen, und normalerweise habe ich etwas verpasst. Ich kann einfach nicht sehen, was es in diesem Fall sein könnte.

Irgendwelche Gedanken? Danke vielmals..

Auf Vorschlag von Raphael habe ich einen früheren Kommentar in diese Antwort umgewandelt.

Es ist nicht so , dass . Tatsächlich ist definition ( f ( n ) ) = O ( f ( n ) ) ∩ Ω ( f ( n ) ) per Definition. Wir haben also Θ ( 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))$

Stellen Sie sich das so vor: Jede Funktion, die "nicht schlechter als n" und "nicht besser als n" macht, ist auch eine Funktion, die "nicht schlechter als n" macht. Der Teil "nicht besser als n" ist nur eine zusätzliche Einschränkung. Dies ist eine einfache Anwendung der logischen Regel, die besagt: . Nach dieser Überlegung sind alle Funktionen, die in der Menge Θ ( n ) enthalten sind, auch Mitglieder der Menge O ( n ) .$x \wedge y \implies x$$\Theta(n)$$O(n)$