Асимптотика c Обозначения: Нахождение двух констант, таких что n> = n0 - PullRequest
0 голосов
/ 19 февраля 2020

Вот асимптотическая c проблема обозначений:

Пусть g (n) = 27n ^ 2 + 18n и пусть f (n) = 0,5n ^ 2 - 100. Найдите положительные постоянные n0, c1 и c2 такое, что c1f (n) ≤ g (n) ≤ c2f (n) для всех n ≥ n0.

Это решение для тета? Докажу ли я 27n ^ 2 + 18n = Ω (0,5n ^ 2 - 100), а затем докажу (27n ^ 2 + 18n) = O (0,5n ^ 2 - 100)?

В таком случае c1 и c2 не будут 1 и 56 соответственно, а n0 будет выше двух n0, которые я найду?

1 Ответ

0 голосов
/ 19 февраля 2020

Существует бесконечно много решений. Нам просто нужно поиграть с алгеброй, чтобы найти ее.

Первое, что нужно отметить, это то, что и g, и f положительны для всех n≥15. В частности, g (15) = 6345, f (15) = 12,5. (Все меньшие значения n делают f <0.) Это означает, что n0 = 15 может работать нормально, а также любое большее значение. </p>

Следующее примечание g '(n) = 54n + 18 и f' (n) = n.

Поскольку f (15) = 15, выберите c1 = 1.

Доказательство того, что это хороший выбор:

0,5n ^ 2 - 100 ≤ 27n ^ 2 + 18n <=> 26,5n ^ 2 + 18n + 100 ≥ 0

... очевидно, верно для всех n≥ 15.

А как насчет с2? Во-первых, мы хотим, чтобы c2 * f (n) рос как минимум так же быстро, как g: c2f '(n) ≥g' (n) или c2 * n ≥ 54n + 18 при n ≥ 15. Поэтому выберите c2 ≥ 56, что, очевидно, подтверждает это.

К сожалению, c2 = 56 не совсем работает при n0 = 15. Есть другой критерий: c2 * f (15) ≥g (15). Для этого 56 недостаточно велико: 56 * f (15) - только 700; г (15) намного больше.

Оказывается, путем подстановки в вышеприведенном соотношении и немного большей алгебре, что c2 = 508 добивается цели.

Доказательство:

27n ^ 2 + 18n ≤ 508 * (0,5n ^ 2 - 100)
<=> 27n ^ 2 + 18n ≤ 254n ^ 2 - 50800
<=> 227n ^ 2 - 18n - 50800 ≥ 0

При n = 15 это справедливо простой заменой. Для всех больших значений n обратите внимание, что производная lhs 454n - 18 положительна для всех n≥15, поэтому функция также не уменьшается в этой области. Это также делает отношения верными.

Подводя итог, мы показали, что n0 = 15, c1 = 1 и c2 = 508 - это одно решение.

...