Big-Oh, следствие определения

Question

Я потратил много времени на чтение вопросов и ответов о Big-Oh здесь и на math.stackexchange, и мне кажется, что это лучшее место для него, поскольку math.stackexchange, похоже, не любит подобные вопросы.Так что я получил некоторую курсовую работу в университете на моем курсе CS, и я не совсем понимаю это, и надеялся, что вы, ребята, могли бы помочь.Я понимаю, что вопросы «домашней работы» здесь слегка недовольны, поэтому я выбрал другой пример, который является не частью моей курсовой работы, но - это аналогичного стиля.

Итак, вот определение, которое мне было дано в примечаниях:

И вопрос, который мне был задан:

Используя определение 2.5, покажите, что если f (n) равно O (g (n)), то k + f (n) также равно O (g (n)).

Я потратил3 дня поиска в интернете любого ответа на подобные проблемы.Глядя на определение 2.5, он говорит, что f (n) - это O (g (n)), а k + f (n) - это O (g (n)).Мне этого достаточно, но, похоже, я должен доказать, как это происходит.Сначала я подумал, что это должно быть сделано как-то по индукции, но с тех пор решил против этого, и должен быть более простой способ.

Любая помощь будет оценена.Я не ожидаю, что кто-то просто встанет и даст мне ответ.Я бы больше предпочел либо методологию, либо ссылку на то, где я могу изучить технику выполнения этого.Могу я еще раз напомнить вам, что это не моя настоящая курсовая работа, а вопрос похожего стиля.

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

Answer 1

предположим, что f (n) равно O (g (n))
тогда существуют c и a k 's.t. для всех n> k ': f (n) <= cg (n) <br> теперь рассмотрим f (n) + k
пусть d будет s.t k <= d * g (n) для всех n, больших k '<br> что вы знаете, возможно, потому что к находится в O (1)
то
f (n) + k <= cg (n) + dg (n) = (d + c) (g (n)) <br> Затем вы используете определение и подставляете d + c для c, ==> f + k находится в O (g)

Answer 2

f (n) <= cg (n) </p>

k + f (n) <= c'g (n) где c '= ck </p>

, поэтому k + f (n) является O (г (н))

Answer 3

Для чего бы это ни стоило, это несколько надуманное определение обозначения big-O. Более общее и, на мой взгляд, более интуитивное определение состоит в том, что f(n) ~ O(g(n)) как n->a если lim|f(n)/g(n)| <= A как n->a для некоторого конечного действительного числа A.

Важной частью является то, что требуется лимитный контекст. В CS этот предел неявно принимается равным бесконечности (поскольку это то, к чему стремится n при увеличении размера задачи), но в принципе это может быть что угодно. Например, sin(x) ~ O(x) как x->0 (на самом деле это точно асимптотика x; это приближение под малым углом).

Answer 4

Тогда k - это O(1), f(n) - это O(g(n)), затем вы можете суммировать эти значения, тогда у вас есть O(1+g(n)), это O(g(n));

f(n), это O(g(n)) затем k + f(n) также O(g(n)), потому что вы написали в своей книге

Игнорировать добавление константы

Константа всегда игнорируется, потому что не может измениться Big-O , любая константа O(1) в Big-O.