О-нотация

Для выражения характеристик быстродействия в вычислительной технике используется короткая схема – О-нотация (big-Oh notation). В этой нотации используется специальная математическая функция от N, т. е. количества исходных данных, которому пропорционально быстродействие алгоритма. Утверждается, что алгоритм принадлежит к классу О(f(N)), где f(N) – некоторая функция от N. Приведенное обозначение читается как «О большое от f(N)» или, менее строго, «пропорционально f(N)»

Например, исследования показали, что алгоритм А принадлежит к классу О(N), а алгоритм В – к классу О(log(N)). Поскольку для положительных чисел log(N) < N, можно сделать вывод о том, что алгоритм В всегда эффективнее алгоритма А.

О-нотация подчиняется простым арифметическим правилам. Во-первых, умножение математической функции внутри скобок в О-нотации на константу не оказывает никакого влияния на О-нотацию. Например, О(3f(N)) и О(24f(N)) эквивалентно О(f(N)), поскольку константы 3 или 24 можно без последствий вынести за скобки как коэффициент пропорциональности, который игнорируется.

Во-вторых, О-нотация демонстрирует асимптотическое поведение, проявляющееся в том, что для больших значений N О-нотация определяет тот класс алгоритма, к которому принадлежит его доминантная часть. Пусть некоторый алгоритм принадлежит к классу О(N² + N). Если величина N достаточно велика, то влияние члена «+N» поглощается членом «N²». Другими словами при больших значениях N алгоритм О(N² + N) эквивалентен алгоритму О(N²). То же можно сказать и для более высоких степеней N.

Предположим, что есть алгоритм, который выполняет три различных задачи. Первая задача выполняется алгоритмом класса О(N), вторая – алгоритмом класса О(N²), третья – алгоритмом класса О(log(N)). Каково будет быстродействие алгоритма в целом. Ответ будет О(N²), поскольку к этому классу принадлежит доминантная часть алгоритма.

Таким образом, значения О большого характеризуют алгоритм для больших значений N, а для маленьких значений N О-нотация не имеет смысла.