С ростом n время вычисления t_T(n) обычно растет. Для конкретной модели вычисления зачастую проще и нагляднее сравнивать не сами времена, а их верхние оценки.

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

В качестве примеров можно привести следующие две известные таблицы (они приведены во многих учебниках по теории сложности).

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

В этой таблице отражено влияние совершенствования ЭВМ на возможности алгоритмов.

Эти таблицы, в частности, иллюстрируют различие между полиномиальными и экспоненциальными алгоритмами. Тем самым аргументируется внимание к разделению алгоритмов на классы по трудоемкости.

Заметим еще, что это различие имеет и другую сторону. Вспомним, например задачу о камнях. Всего различных способов разбиения кучи из n камней на две части - 2ⁿ. Пусть просмотр одного варианта требует O(n) тактов работы, например, МТ. Тогда самый простой способ решения задачи - перебор всех возможных вариантов - потребует O(n) 2ⁿ тактов работы.

Это обычная ситуация. Она может быть проиллюстрирована и на других упомянутых выше примерах. Поэтому экспоненциальные алгоритмы ассоциируются с простым полным перебором вариантов (отсюда и термин переборный алгоритм).(Конечно, не все переборные алгоритмы имеют экспоненциальную сложность!)

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

Более подробные примеры рассмотрены в следующем разделе.

Сложность алгоритмов некоторых задач.

Данный раздел содержит примеры алгоритмов, иллюстрирующих проведенные выше рассуждения. Также алгоритмы и задачи этого разделы будут использованы в дальнейшем при обсуждении классов сложности задач. Этот раздел ни в коем случае не является попыткой обзора алгоритмов и методов их построения. (Такая попытка сделана, например, в [5], а монографии  [1] и [4] целиком посвящены описанию алгоритмов и методов их построения). Более того, примеры этого раздела в большинстве своем либо очевидны, либо знакомы вам из курса дискретной математики.

Далее коротко приводится алгоритм и оценка его сложности «в худшем». Описание задач, а также обозначение их параметров приведены выше.

Задача нахождения максимального числа.

Решение дает очевидный простой алгоритм: последовательно сравниваем числа и в отдельной ячейке храним максимальное из просмотренных. Для решения необходимо просмотреть все числа, т.е. сделать не менее  n-1 сравнений. Но за  n-1 сравнений мы найдем решение задачи. Поэтому данный алгоритм позволяет найти сложность задачи, т.е сложность алгоритма - O(n) является одновременно и сложностью задачи нахождения максимального числа. Верхняя и нижняя оценка сложности совпадают.

Задача сортировки.

В дискретной математике сортировке подлежат объекты разной природы. Пусть необходимо отсортировать (например, по возрастанию) числовой массив из n элементов. Без ограничения общности будем считать, что – степень двойки (чтобы не возиться с целыми частями). В качестве элементарной операции используется операция сравнения чисел. Чтобы сравнивать числа нужно их различать как объекты сортировки (эти объекты имеют численные значения). Сравнение – это операция с результатом «да» или «нет», поэтому кодируем объекты сортировки бинарными последовательностями. Какова минимальная длина такой последовательности для множества их M элементов? Очевидно, что это  log M. В теории информации этот факт известен как энтропия по Хартли.

Если мы упорядочиваем  n  объектов (чисел), то в зависимости от их значений можно получить n! различных упорядочиваний. Последовательность сравнений для их различения не может быть меньше log(n!). Применяем формулу Стирлинга: log(n!)=(n+1/2)logn-n+0,5log2π+α/(12n), 0< α <1, n→∞ . Отсюда следует, что задачу сортировки нельзя решить со сложностью алгоритма, меньшей  O(nlogn).

C 1950-х годов разработано много методов сортировки со сложностью алгоритма, равной O(nlogn).

Задача о камнях.

Здесь тоже дан массив из n чисел, но его не нужно упорядочивать или искать в нем число. Нужно попробовать разложить его на две «максимально» равные части. Каждая из этих частей является подмножеством всего множества камней и полностью определяет другую (оставшиеся камни). Всего подмножеств, как вы знаете, 2ⁿ. На сегодняшний день не существует алгоритма решения этой задачи, отличного от полного перебора. Перебирая последовательно все подмножества мы сравниваем их вес с числом (S a_i)/2). Если получили совпадение, то ответ «да», если же такого совпадения мы не получаем после того, как все множества просмотрены, то ответ «нет». Сложность такого алгоритма O(n2ⁿ).

Простота числа.

Пусть дано натуральное N. Тогда длина входа задачи: n=logN.

Из школы известно два алгоритма: простой перебор и решето Эратосфена.

В первом случае нужно осуществить n^1/2 делений. Сложность алгоритма t(n)=2^n/2.

Можно показать, что сложность алгоритма решето Эратосфена составляет O(2ⁿlog n) операций в модели вычислений RAM, или O(2ⁿ n(log n)) битовых операций, при условии вычисления и зачеркивания каждого кратного числа за время O(1). Таким образом, другая из приведенных в качестве примеров задач – задача о разложении числа на множители – тоже имеет экспоненциальную сложность, так как задача о простоте – это частный случай.