Учебное пособие C#. Алгоритмы и структуры данных н. А. Тюкачев, В. Г. Хлебостроев издание третье, стереотипное 1 / 23

Определение. 
O(g(N)) – это множество функций f(N) таких, что существуют констан-
ты c и N
0
, что 0 ≤ f(N) ≤ c·g(N) для всех N > N
0
.
Таким образом, O-нотация используется для обозначения асимптоти-
ческого верхнего предела для некоторого множества функций. Применитель-
но к скорости роста алгоритма в качестве таких функций выступают зависи-
мости среднего времени выполнения алгоритма от размерности задачи. Рису-
нок 1.1 иллюстрирует понятие O-нотации. На нем по оси ординат отложено 
время выполнения алгоритма, а по оси абсцисс – размерность задачи. Штри-
ховой вертикальной линией показано граничное значение N
0
, с которого на-
чинает выполняться неравенство f(N) ≤ c·g(N). 
Рис. 1.1. Иллюстрация понятия O-нотации 
7 / 23

---

8 
Использование О-нотации избавляет от необходимости при анализе ал-
горитма включать в рассмотрение детали его реализации (язык программиро-
вания, среду выполнения, технические особенности компьютера). Выражение 
«скорость роста алгоритма равна O(g(N))» не зависит от входных данных и 
полезно для распределения алгоритмов по категориям, независимо от вход-
ных данных и деталей реализации.
Зная скорость роста алгоритма, можно прогнозировать, во сколько раз 
увеличится время выполнения алгоритма при кратном увеличении размерно-
сти задачи. В таблице 1.1 показано, как сказывается удвоение размерности 
задачи на времени выполнения алгоритмов с различными скоростями роста 
[40]. 
Таблица 1.1.
Изменение времени выполнения алгоритма
Скорость роста Степень влияния на время выполнения 
O(1) 
Нет влияния 
O(log
2
N) 
Небольшой рост 
O(N) 
Удвоение 
O(N∙log
2
N) 
Немного больше удвоения 
O(N
3/2
) 
Почти в 3 раза 
O(N
2
) 
Увеличение в 4 раза 
O(N
3
) 
Увеличение в 8 раз 
O(2
N
) 
Увеличение в 2
N 
раз 
В теории алгоритмов принято деление задач на [27]:
− задачи класса P, для которых существуют алгоритмы со скоро-
стью роста O(N
k
), т.е. с полиномиальным временем выполнения; 
− задачи класса NPC, для которых не существует алгоритмов с по-
линомиальным временем выполнения, так называемые NP-
полные задачи. 
Подавляющее большинство практически значимых задач относится к 
первому классу, причем с невысокой степенью k.