Я действительно не понимаю, как и что я должен доказать. Я исследовал в каждом, но все еще неясный для меня, что ожидается.Не совсем понимаю нотацию
Какое из следующих утверждений верно? Докажите свои ответы.
- N² ∈ O (n³)
- N² ∈ Ом (n³)
- 2ⁿ ∈ Θ (2 п + 1)
- п! ∈ Θ ((п + 1)!)
Любая помощь будет высоко ценится!
Поскольку это (возможно, домашнее задание) вопросы - это несколько дней назад, я думаю, что я могу ответить на этот вопрос короче.
Википедию страницы (и, надеюсь, ваш учебник и/или примечания тоже) говорит
f(n) ∈ O(g(n)) ⇔ lim sup |f(n)/g(n)| < ∞
f(n) ∈ Ω(g(n)) ⇔ lim sup |f(n)/g(n)| > 0
f(n) ∈ Θ(g(n)) ⇔ f(n) ∈ O(g(n)) and f(n) ∈ Ω(g(n))
Для доказательства левой стороны вы можете доказать правую сторону.
n² ∈ O(n³) верно, из-за
lim sup |n²/n³| = lim (n²/n³) = lim (1/n) = 0 < ∞
n² ∈ Ω(n³) является ложным, из-за
lim sup |n²/n³| = lim (n²/n³) = lim (1/n) = 0
2ⁿ ∈ Θ(2n+1) верно, из-за
0 < lim sup |2ⁿ/2<sup>n+1</sup>| = lim (2ⁿ/(2⋅2ⁿ) = lim (1/2) = 1/2 < ∞
n! ∈ Θ((n+1)!) ложна, из-за
lim sup |n!/(n+1)!| = lim (n!/((n+1)⋅n!) = lim (1/(n+1)) = 0
Примечание: Все ограничения имеет место для n → ∞.
Предположительно, у вас есть учитель или, по крайней мере, какой-то материал, объясняющий большие о-ноты, и им не было предоставлено это задание без контекста. – chepner
Я понимаю большую нотацию, но я не понимаю, как доказать, что n^2 существует в O (n^3) –
Как я понимаю, вам просто нужно сказать для каждого утверждения «true» или «false» и докажите, что ваш ответ правильный. – AbcAeffchen