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

Пример: N²+N+100 = O(N²)

Все классы сложности находятся в иерархическом отношении: одни включают в себя другие. Однако про большинство включений неизвестно, являются ли они строгими.

Выделяют следующие типичные виды сложности алгоритмов.

Классы сложности алгоритмов в зависимости от функции трудоемкости
Вид f(n)	Характеристика класса алгоритмов
	Большинство инструкций большинства функций запускается один или несколько раз. Если все инструкции программы обладают таким свойством, то время выполнения программы постоянно.
log N	Когда время выполнения программы является логарифмическим, программа становится медленнее с ростом N. Такое время выполнения обычно присуще программам, которые сводят большую задачу к набору меньших подзадач, уменьшая на каждом шаге размер задачи на некоторый постоянный фактор. Будем рассматривать время выполнения, являющееся небольшой по величине константой. Изменение основания не сильно сказывается на изменении значения логарифма: при N=1 000, log N = 3, если основание равно 10, или порядка 10, если основание равно 2; когда N=1 000 000, значения log N увеличивается в два раза. При удвоении значения параметра log N растет на постоянную величину, а удваивается лишь тогда, когда N достигает N2.
N	Когда время выполнения программы является линейным, это обычно значит, что каждый входной элемент подвергается небольшой обработке. Когда N равно миллиону, таким же и является время выполнения. Когда N удваивается, то же происходит и со временем выполнения. Эта ситуация оптимальна для алгоритма, который должен обработать N вводов (или произвести N выводов).
N log N	Время выполнения, пропорциональное N log N, возникает тогда, когда алгоритм решает задачу, разбивая ее на меньшие подзадачи, решая их независимо и затем объединяя решения. Время выполнения такого алгоритма равно N log N. Когда N=1 000 000, . Когда N удваивается, тогда время выполнения более чем удваивается.
N2	Когда время выполнения алгоритма является квадратичным, он полезен для практического использования при решении относительно небольших задач. Квадратичное время выполнения обычно появляется в алгоритмах, которые обрабатывают все пары элементов данных (возможно, в цикле двойного уровня вложенности). Когда N=1 000, время выполнения равно одному миллиону. Когда N удваивается, время выполнения увеличивается вчетверо.
N3	Похожий алгоритм, который обрабатывает тройки элементов данных (возможно, в цикле тройного уровня вложенности), имеет кубическое время выполнения и практически применим лишь для малых задач. Когда N=100, время выполнения равно одному миллиону. Когда N удваивается, время выполнения увеличивается в восемь раз.
2N	Лишь несколько алгоритмов с экспоненциальным временем выполнения имеет практическое применение, хотя такие алгоритмы возникают естественным образом при попытках прямого решения задачи, например полного перебора. Когда N=20, время выполнения имеет порядок одного миллиона. Когда N удваивается, время выполнения увеличивается экспоненциально.

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

Класс Р – это класс рациональных или полиномиальных алгоритмов, функция трудоемкости которых определяется полиномиально от входных параметров. Например, O(N), O(N²), O(N³).

Класс L – это класс субэкспоненциальных алгоритмов со степенью трудоемкости O(N log N).

Класс E – это класс собственно экспоненциальных алгоритмов со степенью трудоемкости O(2^N).

Класс F – это класс собственно надэкспоненциальных алгоритмов. Существуют алгоритмы с факториальной трудоемкостью, но они в основном не имеют практического применения.

Ниже приведен ряд задач полиномиальной сложности:

- задача сортировки;

- задача поиска эйлерова цикла на графе;

- поиск некоторого слова в тексте длиной n символов;

- поиск кратчайшего пути на графе;

- линейное программирование.

Задачи класса E представляют наибольшую сложность в решении. Для нахождения ответа на такую задачу необходимо выполнить fⁿ операций, причем n – размерность входных данных, а f может быть константой, полиномом или сложным фукционалом.