Что такое порядковая запись f (n) = O (g (n))?

Question

Вопрос 1: При каких обстоятельствах O(f(n)) = O(k f(n)) будет наиболее подходящей формой анализа сложности времени?

Вопрос 2: Работа с математическим определением записи O, как показать это O(f(n)) = O(k f(n)), для положительной постоянной k?

По первому Вопросу я думаю, что это средняя и наихудшая форма сложности времени. Я прав? И что еще мне в этом написать?

По второму Вопросу, я думаю, нам нужно определить функцию математически. Так что ответ примерно такой, потому что умножение на константу просто соответствует перенастройке значения произвольной константы k в определении O?

Answer 1

Мой взгляд: для первого я думаю, что это это средний случай и форма наихудшего случая время сложность. я прав? и что еще я пишу в этом?

Нет! Обозначение Big O НЕ имеет никакого отношения к среднему или наихудшему случаю. Речь идет только о порядке роста функции - в частности, о том, как быстро функция растет относительно другой функции. Функция f может быть O(n) в среднем случае и O(n^2) в худшем случае - это просто означает, что функция ведет себя по-разному в зависимости от своих входов, и поэтому два случая должны учитываться отдельно.

Относительно вопроса 2, для меня очевидно из формулировки вопроса, что вам нужно начать с математического определения Большого О. Для полноты, это:

Формальное определение: f (n) = O (g (n)) означает, что есть положительные константы с и k, так что 0 ≤ f (n) ≤ cg (n) для все n ≥ k. Значения c и k должны быть фиксированным для функции f и должен не зависит от.

(источник http://www.itl.nist.gov/div897/sqg/dads/HTML/bigOnotation.html)

Итак, вам нужно работать с этим определением и написать математическое доказательство, показывающее, что f(n) = O(k(n)). Начните с замены O(g(n)) на O(k*f(n)) в определении выше; остальное должно быть довольно легко.

Answer 2

Вопрос 1 немного расплывчат, но вашего ответа на вопрос 2 явно не хватает. Вопрос гласит «работа с математическим определением нотации». Это означает, что ваш инструктор хочет, чтобы вы использовали математическое определение:

f (x) = O (g (x)) тогда и только тогда, когда предел [x -> a +] | f (x) / g (x) | <бесконечность, для некоторых </p>

И он хочет, чтобы вы включили g (x) = kf (x) и докажите, что это неравенство выполнено.

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