est-il

J'ai donc cette question pour prouver une déclaration:

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

Je n'ai pas besoin de savoir comment le prouver, juste que dans mon esprit cela n'a aucun sens et je pense que ce devrait plutôt être $\Theta(n)\subset O(n)$ .

Ma compréhension est que $O(n)$ est l'ensemble de toutes les fonctions qui ne font pas pire que $n$ tandis que $\Theta(n)$ est l'ensemble de toutes les fonctions qui ne font pas mieux et pas pire que n.

En utilisant cela, je peux penser à l'exemple d'une fonction constante, disons $g(n)=c$ . Cette fonction sera sûrement un élément de $O(n)$ car elle ne fera pas pire que $n$ lorsque $n$ approche d'un nombre suffisamment grand.

Cependant, la même fonction ne serait pas un élément de Θ ( n ) car g fait mieux que n pour les grands n ... Alors puisque g ∈ O ( n ) et g ∉ Θ ( n ) , alors O ( n ) ∉ Θ ( n $g$$\Theta(n)$$n$$n$$g \in O(n)$$g \not\in \Theta(n)$$O(n)\not\in\Theta(n)$

La question est-elle donc peut-être fausse? J'ai appris qu'il est dangereux de faire cette supposition et généralement j'ai oublié quelque chose, je ne vois tout simplement pas ce que cela pourrait être dans ce cas.

Des pensées ? Merci beaucoup..

À la suggestion de Raphaël, j'ai transformé un commentaire précédent en cette réponse.

Il n'est pas vrai que . En fait, Θ ( f ( n ) ) = O ( f ( n ) ) ∩ Ω ( f ( n ) ) , par définition. Nous avons donc Θ ( 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))$

Pensez-y de cette façon: chaque fonction qui ne fait "pas pire que n" et "pas mieux que n" est également une fonction qui ne fait "pas pire que n". La partie "pas mieux que n" n'est qu'une contrainte supplémentaire. Il s'agit d'une application simple de la règle logique qui dit: . Par ce raisonnement, toutes les fonctions qui sont dans l'ensemble Θ ( n ) sont également membres de l'ensemble O ( n ) .$x \wedge y \implies x$$\Theta(n)$$O(n)$