<= vs <при доказательстве биг-о нотации

Question

Мы только начали изучать биг-о в классе. Я понимаю общую концепцию, согласно которой f (x) является биг-о из g (x), если существуют две константы c, k, такие что для всех x> k | f (x) | <= c | g (x) |. У меня возник вопрос, нужно ли включать <= для подписи или достаточно просто поставить <знак? </p>

Например: предположим, что f (x) = 17x + 11, и мы должны доказать, что это O (x ^ 2). Тогда, если мы возьмем c = 28 и x> k = 1, мы знаем, что 17x + 11 <= 28x ^ 2. Так как мы знаем, что x всегда будет больше 1, это означает, что 28x ^ 2 всегда будет больше 17x + 11. Итак, действительно ли нам нужно включить знак равенства (<=), или это нормально, если мы просто напишем (<)? </p>

Заранее спасибо.

Answer 1

С | f ( x ) |≤ c | g ( x ) |для некоторой вещественной c следует, что | f ( x ) |<(<em> c + e ) | g ( x ) |для всех e > 0.

Из этого следует, что существует c ' = ( c + e ) такой, что | f ( x ) |<<em> c ' | g ( x ) |, так что вы можете использовать <вместо ≤. </p>

Более практично, если вы можете доказать| f ( x ) |<<em> c | g ( x ) |, часть ≤ следует тривиально.

Answer 2

не нормально использовать < вместо ≤, хотя очевидно, что в некоторых случаях они идентичны, поскольку ≤ является частью нотации Big-Oопределение.

С другой стороны, определение: 0 ≤ f(n) < cg(n) принадлежит другому классу (обозначение Little-o), который входит в класс Big-O

Answer 3

Нельзя заменить <= на <в определении. </p>

Любая функция f, которая бесконечно часто равна нулю, равна O (f), но не если вы замените <= на <. </p>

Например, пусть f (x) = x, если x нечетно, 0, если x четно. Тогда f есть O (f), потому что f (x) <= f (x) для всех x. Однако нет такого c, что f (x) <cf (x) для всех больших x, потому что обе стороны равны 0 для всех четных x. </p>

Answer 4

требуется ли нам включать знак <= или достаточно просто поставить знак <*? 1002 * </blockquote>

Есть две слегка разные вещи, которые вы спрашиваетездесь, я думаю:

• Если вы можете продемонстрировать c и k такие, что для всех x > k |f(x)| <= c|g(x)|, то тривиально у вас есть также продемонстрировали c и k такие, что для всех x > k |f(x)| < c|g(x)|.Таким образом, , показывающий <, является достаточным , но:

• Как вы заявили, фактическое требование для возможности сказать f(x) = O(g(x)) это найти c и k такие, что для всех x > k |f(x)| <= c|g(x)|.Если лучшее, что мы можем сделать, - это найти c и k, такие что для всех x > k |f(x)| = c|g(x)|, то мы не выполнили ваше условие <, но мы сделали достаточнопоказать f(x) = O(g(x)).Так что показ < не необходимо

Answer 5

Если вы показали x