Что такое простой способ найти C и N при доказательстве алгоритма Big-Oh?

Я начинаю узнавать о нотации Big-Oh.

Что такое простой способ найти C и N ₀ для данной функции?

Скажем, например:

(n + 1) ⁵ или n ⁵ + 5n ⁴ + 10n ² + 5n + 1

Я знаю, что формальное определение для Big-Oh:

Пусть f (n) и g (n) - отображение функций неотрицательные целые числа к действительным числам. Будем говорить, что f (n) есть O (g (n)), если - вещественная постоянная s > 0 и целочисленная константа N ₀ >= 1 такой, что f (n) <= cg (n) для любого целого N > N ₀.

Мой вопрос: какой хороший, надежный метод для выбора значений для c и N ₀?

Для данного многочлена выше (n + 1) ⁵ я должен показать, что это O (n ⁵). Итак, как мне выбрать мои c и N ₀, чтобы я мог сделать указанное выше определение истинным, не догадываясь?

Ответ 1

Вы можете выбрать константу c, добавив коэффициенты каждого члена в ваш многочлен. Так как

| n ⁵ + 5n ⁴ + 0n ³ + 10n ² + 5n ¹ + 1n ⁰ | <= | n ⁵ + 5n ⁵ + 0n ⁵ + 10n ⁵ + 5n ⁵ + 1n ⁵ |

и вы можете упростить обе стороны, чтобы получить

| n ⁵ + 5n ⁴ + 10n ² + 5n + 1 | <= | 22n ⁵ |

Итак, c = 22, и это всегда будет справедливо для любого n >= 1.

Почти всегда можно найти нижний c, подняв N ₀, но этот метод работает, и вы можете сделать это в своей голове.

(Операции абсолютного значения вокруг полиномов должны учитывать отрицательные коэффициенты.)

Ответ 2

Обычно доказательство проводится без сбора бетона С и №. Вместо доказательства f (n) C * g (n) вы доказываете, что f (n)/g (n) С.

Например, для доказательства n ³ + n является O (n ³), вы делаете следующее:

(n ³ + n)/n ³= 1 + (n/n ³) = 1 + (1/n ²) < 2 для любого n >= 1. Здесь вы можете выбрать любой C >= 2 с No = 1.

Ответ 3

Вы можете проверить, что lim abs (f (n)/g (n)) при n → + infitity, и это даст вам константу (g (n) в вашем примере n ^ 5, f ( n) является (n + 1) ^ 5).

Заметим, что значение Big-O при x → + бесконечности состоит в том, что если f (x) = O (g (x)), то f (x) "растет не быстрее g (x)", поэтому вам просто нужно доказать, что lim abs (f (x)/g (x)) существует и меньше + бесконечности.

Ответ 4

Это сильно зависит от функции, которую вы рассматриваете. Однако для данного класса функций вы можете придумать алгоритм.

Например, полиномы: если вы установите C на любое значение, большее, чем старший коэффициент многочлена, то вы можете решить для N ₀.

Ответ 5

После того, как вы понимаете магию, вы также должны получить, что big-O - это нотация. Это означает, что вам не нужно искать эти коэффициенты при решении каждой проблемы, как только вы убедитесь, что поняли, что происходит за этими письмами. Вы должны просто управлять символами согласно значению, согласно его правилам.

Нет простого универсального правила для определения действительных значений N и c. Вы должны вспомнить свое знание исчисления, чтобы решить его.

Определение big-O запутано с определение предела. Это делает c удовлетворяющим:

c > lim | f (n)/g (n) |, учитывая n подходов + бесконечность.

Если последовательность ограничена сверху, она всегда имеет предел. Если это не так, то f не является O (g). После того, как вы выбрали конкретный c, у вас не будет проблем с поиском подходящего N.