Есть

Итак, у меня есть этот вопрос, чтобы доказать утверждение:

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

Мне не нужно знать, как это доказать, просто, на мой взгляд, это не имеет смысла, и я думаю, что это должно быть .$\Theta(n)\subset O(n)$

Насколько я понимаю, - это набор всех функций, которые работают не хуже а - это набор всех функций, которые работают не лучше и не хуже, чем n.n Θ ( n $O(n)$$n$$\Theta(n)$

Используя это, я могу вспомнить пример постоянной функции, скажем, . Эта функция, безусловно, будет элементом как она будет работать не хуже, чем когда приближается к достаточно большому числу.O ( n ) n $g(n)=c$$O(n)$$n$$n$

Однако та же функция не будет элементом как g делает лучше, чем для больших ... Тогда, поскольку и тогдаthetas ; ( п ) п п г ∈ O ( п ) г ∉ & thetas ; ( п ) О ( п ) ∉ & thetas ; ( п $g$$\Theta(n)$$n$$n$$g \in O(n)$$g \not\in \Theta(n)$$O(n)\not\in\Theta(n)$

Так что, возможно, вопрос не так? Я понял, что делать такое предположение опасно, и обычно я что-то упустил, я просто не понимаю, что это может быть в этом случае.

Есть идеи ? Большое спасибо..

По предложению Рафаэля я превратил предыдущий комментарий в этот ответ.

Это не верно , что . В самом деле, Θ ( F ( п ) ) = O ( F ( п ) ) ∩ Ом ( е ( п ) ) , по определению. Таким образом , мы имеем thetas ; ( п ( п ) ) ⊂ O ( F ( п ) ) .$O(f(n)) \subset \Theta(f(n))$$\Theta(f(n)) = O(f(n)) \cap \Omega(f(n))$$\Theta(f(n)) \subset O(f(n))$

Подумайте об этом так: каждая функция, которая выполняет «не хуже, чем n» и «не лучше, чем n», также является функцией, которая выполняет «не хуже, чем n». Часть «не лучше, чем n» - это просто дополнительное ограничение. Это прямое применение логического правила, которое гласит: . По этой причине все функции, входящие в набор Θ ( n ) , также являются членами набора O ( n ) .$x \wedge y \implies x$$\Theta(n)$$O(n)$