Асимптоти c Обозначения: Доказательство Большой Омеги, О и Тета

Question

У меня есть несколько асимптотических c проблем с обозначениями У меня не совсем gr asp.

Итак, доказывая асимптотику c сложности, я понимаю операции нахождения константы и n0-члена, для которого обозначения будут истинными. Так, например:

Prove 7n+4 = Ω(n)

В таком случае мы бы выбрали постоянную c, такую, чтобы она была ниже 7, поскольку это касается Большой Омеги. Выбор 6 приведет к

7n+4 >= 6n

n+4 >= 0

n = -4

Но так как n0 не может быть отрицательным термином, мы выбираем положительное целое число, поэтому n0 = 1.

Но как насчет такой проблемы:

Prove that n^3 − 91n^2 − 7n − 14 = Ω(n^3).

Я выбрал 1/2 как константу, достигнув

1/2n^3 - 91n^2 - 7n -14 >= 0.

Но я не уверен, как продолжить. Кроме того, проблема, подобная этой, я думаю относительно тета:

Let g(n) = 27n^2 + 18n and let f(n) = 0.5n^2 − 100. Find positive constants n0, c1 and c2 such
that c1f(n) ≤ g(n) ≤ c2f(n) for all n ≥ n0.

В таком случае я выполняю здесь две отдельные операции, одно сравнение с большим О и одно сравнение с большой Омегой, так что существует отношение тета или тесно связаны? Если так, как бы я go об этом?

Answer 1

Чтобы показать n ³ - 91n ² - 7n - 14 в Ω (n ³ ), нам нужно выставить некоторые числа n ₀ и c такие, что для всех n ≥ n ₀ :

n ³ - 91n ² - 7n - 14 ≥ cn ³

Вы выбрали c = 0,5, так что давайте go с этим. Изменение порядка дает:

n ³ - 0,5n ³ ≥ 91n ² + 7n + 14

Умножение обеих сторон на 2 и упрощение:

182n ² + 14n + 28 ≤ n ³

Для все n ≥ 1, мы имеем:

182n ² + 14n + 28 ≤ 182n ² + 14n ² + 28n ² = 224n ²

А когда n ≥ 224, мы имеем 224n ² ≤ n ³ . Следовательно, выбор n ₀ = 224 и c = 0,5 показывает, что исходная функция находится в Ω (n ³ ).