Обозначение Big O - что означает натуральное число M и постоянный фактор C?

Question

Я понимаю, что такое Big O Notation, когда дело доходит до определения сложности или наихудшего случая на основе выдержки из кода.

В классе меня учили, что когда дело доходит до сложности и обозначения Big O, мы игнорируем маленькие аргументы n, которые ниже M и постоянные факторы C.

Это было дано мне в классе:

В записи Big-Oh.Пусть f функция от N до положительных вещественных величин.(Думайте о f (n) как о времени выполнения для аргумента размера n. Это может быть наихудший случай или средний случай.) Пусть g - еще одна такая функция.Мы говорим, что f ∈ O (g), когда существует некоторое натуральное число M и постоянный фактор C, такой что для всех n> M имеем f (n) <= C × g (n).В логических символах: ∃M.∃C.∀n> M. f (n) <= C × g (n) </p>

Могу ли я узнать, что означает это утверждение, в частности:

1. Почему мы говорим:

Пусть f - функция от N до положительных вещественных чисел.

Почему это означает:

Пусть g еще одна такая функция.

Что это значит:

Мы говорим, что f ∈ O (g), когда существует некоторое натуральное число M и постоянный фактор C, такой что для всех n> M,имеем f (n) <= C × g (n).В логических символах: ∃M.∃C.∀n> M. f (n) <= C × g (n) </p>

Как эти вышеприведенные выдержки связаны с игнорированием небольших аргументов и постоянных факторов C?

Answer 1

Подводя итог: C раз g в конечном итоге доминирует f.

1 & 2.

Пусть f - функция от N до положительных вещественных чисел.(Думайте о f (n) как о времени выполнения для аргумента размера n. Это может быть наихудший случай или средний случай.) Пусть g - еще одна такая функция.

ОК: f и g - функции от натуральных чисел (N) до положительных вещественных чисел.Почему из натуральных чисел?Мы предполагаем, что размер аргумента - это то, что мы можем точно указать.Натуральное число - это то, что мы можем точно указать.Реального числа нет.Почему положительные отзывы?Мы предполагаем, что время выполнения не обязательно является чем-то, что мы можем точно указать.

Но здесь важно не то, что говорится, а то, что говорится , а не .Никто не сказал, что f является монотонно возрастающим, или что g является полиномом, или что-то еще.Все, что мы знаем, это то, что f и g являются функциями .Это почти все, что нужно сделать.Да, они отображают натуральные и положительные реалы, но это довольно небольшое ограничение.Итак, суть в том, что есть много, много функций f и g на выбор.Единственное несколько важное ограничение состоит в том, что вещественных чисел намного больше, чем натуральных.

3.

Мы говорим, что f ∈ O (g), когда существует некоторое натуральное число M и константамножитель C такой, что для всех n> M имеем f (n) <= C × g (n).В логических символах: ∃M.∃C.∀n> M. f (n) <= C × g (n) </p>

M и C являются константами.Мы выбираем М и С, и мы сделали.Важным моментом здесь является то, что в имеется по крайней мере один M и по крайней мере один C , который удовлетворяет предложению.Не: любой M или любой C. Утверждение состоит в том, что существует как минимум один таких M и C.

n наС другой стороны, не является константой.Мы можем выбрать n как любое число, если оно больше, чем M. В заявлении говорится, что для любого выбора n (больше, чем M) можно найти хотя бы одно значение C, так чтоесли вы умножите g (n) на C, этот продукт будет больше, чем f (n).Не имеет значения , что такое n, если оно больше, чем M.

Причина, по которой мы учитываем константы M и C, становится ясной, когда мы предполагаем, что одно из ограничений было снято.Предположим, что утверждение ничего не говорит о M:

Мы говорим, что f ∈ O '(g), когда существует некоторый постоянный фактор C, такой, что для всех n имеем f (n) <= C× г (н).В логических символах: ∃C.Fnf (n) <= C × g (n) </p>

Теперь это говорит: рассмотрим пространство всех возможных выходов f и всех возможных выходов g.Если мы «расширим» пространство выходов g константой C, каждый из них будет больше, чем любая из точек в f.Теперь это более сильное утверждение, чем когда мы указали M. Что если f (0) = 10 и g (0) = 0?Теперь может быть нет C, что составляет Cg(0) > Cf(0).Итак, М «обрезает» эти плохие грани.

На этой странице также есть отличное объяснение и наглядность: https://xlinux.nist.gov/dads/HTML/bigOnotation.html

Answer 2

Для (1) и (2): Как правило, в доказательстве или в определении текст Let x be a Y является частью демонстрации того, что все x, которые удовлетворяют условию Y, имеют дополнительныйсвойство Z. Доказательство покажет, что заключение Z верно для X. Тогда , поскольку на X не было указано никаких условий, кроме Y , делается вывод, что для всех X, имеющих условие Y, условие Zтакже верно.

Вам придется работать через (3) самостоятельно.Нет замены, кроме как разбить это утверждение на более мелкие части, составить представление о каждой из частей, а затем объединить их в понимание всего утверждения.

For (4): константа C появляется всамо утверждение, и особенно важно, что C появляется с экзистенциальным квалификатором:

∃C. ∀n > M. f(n) <= C × g(n)

Это дает значение C в утверждении.Чтобы выразить смысл, нам лучше взглянуть на все утверждение:

∃M. ∃C. ∀n > M. f(n) <= C × g(n)

В центре этого утверждения мы хотим выразить идею, что g «больше», чем f.За исключением того, что нас интересует возможное поведение f и g, а не их поведение при малых значениях.Следовательно, добавление ∃M к утверждению.То есть в конечном итоге g больше, чем f.И нас больше интересует «форма» f и g, которая дает нам постоянную C.

Поучительное упражнение - переписать утверждение с двойными отрицаниями:

~ ~ ∃M. ∃C. ∀n > M. f(n) <= C × g(n)

Затем протолкните второе отрицание через утверждение:

~ ∀M. ∀C. ∃n > M. f(n) > C × g(n)

Затем рассмотрите, что означает утверждение в первом отрицании.