О нотация, разбор определения

#алгоритм

Читаю Седживка, до этого момента было все понятно:


  Говорят, что функция g(N) имеет порядок O(f(N)), если существуют такие
  постоянные c0 и N0, что g(N) < c0 * f(N) для всех N > N0.


Набор слов, объясните пожалуйста что к чему в этом определении.

Гуглил, сложилось мнение что просто отбрасывают все коэффициенты кроме такого, который
растет больше всех при росте входных данных.
    

Ответы

Ответ 1

Нотация O(f) часто используется для описания скорости роста функций в виде O(N)(O(N*N),
O(log(N)) и т.д. и т.п.). Фактически, это означает, что некоторая g(N) возрастает не
быстрее, чем линейная (квадратичная, логарифмическая, ... ) функция от N с некоторыми
коэффициентами.

Например, функция g(N) = 4*N имеет порядок O(N), т.к. мы можем записать соотношение
g(N) < 10*N и это соотношение будет справедливым для любых N > 1. В этом примере c0
= 10, а N0 = 1.

А вот еще один пример, для более сложной функции g. Пусть g(N) = 2*N*N + N. Эта функция
имеет порядок O(N*N), поскольку для любого N > 1 справедливо g(N) < 4*N*N. В этом примере
c0 = 4, а N0 = 1.

На самом деле, параметры c0 и N0 могут быть произвольными, но должны быть конечными
и не зависеть от N.

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

Например, если есть две функции (алгоритма) сортировки массивов, одна из которых
имеет порядок O(N), а другая O(N*N), то первая функция эффективнее чем вторая.


Ответ 2

Ответ верный. Приведу только пример, который, имхо, сделает его чуть понятней.
Пусть g(N) = N*N + log(N) Тогда порядок g(N) будет O(N*N) т.к. при N0 = 1 и C0 =
2 для любого N>N0 g(N) < C0 * N*N истинно.

Просто во всех ранее приводимых примерах f(N) == g(N), что, видимо, немного сбивает
с толку.