Нотация “большое О”¶

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

Хорошей базовой единицей вычисления для сравнения суммирующих алгоритмов, показанных ранее, может служить количество операций присваивания, используемых при подсчёте суммы. В функции sumOfN есть только одно такое присваивание 1 (\(theSum = 0\)) плюс значение n (сколько раз мы вычисляем \(theSum=theSum+i\)). Мы можем обозначить эту величину (назовём её T), где \(T(n)=1 + n\). Параметр n часто называют “размером задания”, так что мы можем прочитать это как “T(n) - это время, необходимое для решения задачи, размером n, за 1+n шагов.”

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

Учёные-информатики при использовании такой техники анализа предпочитают идти на один шаг дальше. Выходит так, что точное количество операций не так важно, как определение наиболее доминирующей части функции \(T(n)\). Другими словами, когда задание становится больше, некая часть функции \(T(n)\), как правило, перекрывает всё остальное. Эта доминирующая часть в итоге и используется при сравнении. Функция порядка величины описывает ту часть \(T(n)\), которая сильнее возрастает при росте n. Порядок величины часто называют нотацией “большое О” (от order - порядок) и записывают как \(O(f(n))\). Он предоставляет целесообразное приближение к действительному числу шагов в вычислении. Функция \(f(n)\) является простым представлением доминирующей части оригинальной \(T(n)\).

В примере выше \(T(n)=1+n\). Чем больше становится n, тем менее значимой для конечного результата становится константа 1. При поиске приближения для \(T(n)\) мы можем отбросить 1 и просто сказать, что временем выполнения является \(O(n)\). Важно отметить, что 1 безусловно важна для \(T(n)\). Однако, при росте n наше приближение останется столь же точным и без неё.

Ещё один пример: предположим, что для некоего алгоритма точное число шагов \(T(n)=5n^{2}+27n+1005\). При малых n (скажем, 1 или 2) константа 1005 выглядит доминирующей частью функции. Однако, с ростом n, превалирующим становится слагаемое \(n^{2}\). Фактически, когда n действительно велико, то два других слагаемых перестают играть хоть какую-нибудь значимую роль в определении конечного результата. Ещё раз, аппроксимируя \(T(n)\) с ростом n, мы можем игнорировать другие слагаемые и сфокусироваться только на \(5n^{2}\). Дополнительно, коэффициент \(5\) тоже становится неважным при увеличении n. Так что мы можем сказать, что функция \(T(n)\) имеет порядок величины \(f(n)=n^{2}\), или просто \(O(n^{2})\).

Хотя мы и не видим этого в примере с суммированием, иногда производительность алгоритма зависит от точных значений данных больше, чем от размера задачи. Для алгоритмов такого рода нам нужно характеризовать их эффективность с точки зрения наилучшего, наихудшего или усреднённого случая. Производительность для худшего случая относится к определённому набору данных, на котором алгоритм выполняется особенно плохо. В то время как различные наборы данных для точно такого же алгоритма могут иметь необычайно хорошую производительность, в большинстве случаев алгоритм имеет производительность где-то по середине между этими двумя экстремумами (усреднённый случай). Учёным-информатикам важно понимать эти различия, чтобы на впасть в заблуждение при рассмотрении одного конкретного случая.

Некоторое количество очень распространённых функций порядка величины будет попадаться вам вновь и вновь в процессе изучения алгоритмов. Все они представлены в Таблице 1. Для того, чтобы увидеть, какая из них является доминирующей частью любое функции \(T(n)\), мы должны видеть, как они соотносятся друг с другом при возрастании n.

На Рисунке 1 показаны графики распространённых функций из Таблицы 1. Обратите внимание, что при малых n функции нелегко отличить друг от друга и тяжело сказать, какая из них доминирует. Однако, как только n вырастает, появляется определённая зависимость, и легко увидеть, как они соотносятся друг с другом.

Рисунок 1: Графики распространённых функций “большое О”

В качестве заключительного примера предположим, что у нас есть фрагмент кода на Python, показанный в Листинге 2. Несмотря на то, что на самом деле эта программа ничего не делает, полезно будет посмотреть, как мы можем взять существующий код и проанализировать его производительность.

Листинг 2

a=5
b=6
c=10
for i in range(n):
   for j in range(n):
      x = i * i
      y = j * j
      z = i * j
for k in range(n):
   w = a*k + 45
   v = b*b
d = 33

Число операций присваивания представляет собой сумму из четырёх слагаемых. Первое - константа 3, представляющая три присваивания в начале фрагмента. Второе - \(3n^{2}\), поскольку три присваивания выполняются \(n^{2}\) раз внутри вложенной итерации. Третье - \(2n\), два присваивания, повторяющиеся n раз. Наконец, четвёртое слагаемое - константа 1, представляющая последний оператор присваивания. Всё вместе это даёт \(T(n)=3+3n^{2}+2n+1=3n^{2}+2n+4\). Глядя на степени, мы легко можем заметить, что слагаемое \(n^{2}\) будет доминантой, и следовательно, этот фрагмент кода является \(O(n^{2})\). Обратите внимание, что прочие слагаемые (так же, как и коэффициенты) можно проигнорировать при возрастании n.

Рисунок 2: Сравнение \(T(n)\) с распространёнными функциями “большого О”

На Рисунке 2 показаны графики нескольких распространённых функций “большое О” в сравнении с обсуждаемой выше функцией \(T(n)\). Обратите внимание, что в изначально \(T(n)\) больше, чем кубическая функция, но с ростом n последняя быстро берёт верх над \(T(n)\) Так же легко увидеть, что \(T(n)\) с ростом \(n\) следует квадратичной функции.