Что на самом деле означает «большой» график

Question

Существует много пояснений о big-0, но я действительно запутался в этой части.

Acoording определению Big-O в этой функции

f (n) ≤ c ·g(n), for n ≥ n0 

“ f (n) is big-Oh of g(n).” 

Но описание функции в терминах большой нотации O обычно только обеспечивает верхнюю границу скорости роста функции.

так и для, например, здесь 34 является верхней гранью множества { 5, 10, 34 }

Так что, если в этом графике, как е (п) O (г (п)), потому что, если я получаю верхнее связанная с функцией g (n), это значение будет отличаться от того, что указано здесь для n> = n0 ..

Answer 1

За пределами n0 f (n) не будет расти быстрее, чем g (n). Скорость роста f (n) в зависимости от n не более g (n).

Скорость роста g (n) называется верхней границей скорости роста f (n) f (n) - Big-O of g (n).

Наихудшая скорость роста f (n) будет не более g (n), так как f (n) является Big-O of g (n).

Это все о знании того, насколько большой f (n) может расти относительно другой известной функции.

Например, если f (n) = n^2, а g (n) - n^3, то тривиально f (n) является Big-O of g (n), так как n^2 никогда не будет расти быстрее чем n^3.

«c» используется для математических доказательств - это просто линейная масштабирующая переменная. Мы не можем просто обойти и заявить, что что-то другое - Big-O. Если мы выберем n0 и с при заданном г (п), и это имеет место равенство

F (п) ≤ С ° г (п) при п ≥ n0

то можно показать, что действительно f (n) является Big-O of g (n).

Пример:

F (п) = п^2;
g (n) = n^3;

Мы можем выбрать n0 = 1 и с = 1, что

F (N) ≤ 1 · г (п) при п ≥ 1

, которая становится

п^2 ≤ 1 · п^3, при п ≥ 1

, который всегда выполняется, таким образом, f (n) доказано, что Big-O для g (n).

Доказательства могут усложняться, например this, но это его суть.