Асимптотический порядок роста

Итак, наше обсуждение вычислительной разрешимости по своей сути базируется на способности выражения того, что худшее время выполнения алгоритма для входных данных размера n растет со скоростью, которая не более чем пропорциональна некоторой функции f (n).

Функция f (n) становится граничной оценкой времени выполнения алгоритма. Теперь нужно заложить основу для дальнейшего рассмотрения этой концепции.

Алгоритмы будут в основном выражаться на псевдокоде наподобие того, который использовался в алгоритме Гейла–Шепли. Время от времени появляется необходимость в более формальных средствах, но для большинства целей такого стиля определения алгоритмов вполне достаточно.

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

Если нам потребуется что-то сказать о времени выполнения алгоритма с входными данными размера n, можно попытаться сделать предельно конкретное заявление, например: «Для любых входных данных размера n этот алгоритм будет выполнен не более чем за 1,62n2 + 3,5n + 8 шагов».

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

Во-первых, получение такой точной оценки может потребовать значительных усилий, а настолько подробная оценка все равно не нужна.

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

И наконец, излишне точные утверждения о количестве шагов алгоритма часто оказываются (в некоторой степени) бессмысленными. Как говорилось ранее, мы обычно подсчитываем шаги в описании алгоритма на псевдокоде, напоминающем язык программирования высокого уровня.

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

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

Например, если для выполнения одной операции языка высокого уровня требуется 25 низкоуровневых машинных команд, то наш алгоритм, выполняемый за максимум 1,62n2 + 3,5n + 8 шагов, может рассматриваться как выполняемый за 40,5n2 + 87,5n + 200 шагов при анализе на уровне, приближенном к уровню физического оборудования.