Полиномиальное время как показатель эффективности

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

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

Для таких задач хороший алгоритм должен обладать более эффективной закономерностью масштабирования; при возрастании размера входных данных с постоянным множителем (скажем, вдвое) время выполнения алгоритма должно увеличиваться с постоянным множителем C. На математическом уровне эта закономерность масштабироваться может быть сформулирована так.

Предположим, алгоритм обладает следующим свойством: существуют такие абсолютные константы c > 0 и d > 0, что для любого набора входных данных N время выполнения ограничивается cNd примитивными вычислительными шагами. (Иначе говоря, время выполнения не более чем пропорционально Nd.)

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

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

Обратите внимание: любая граница с полиномиальным временем обладает искомым свойством масштабирования. Если размер входных данных возрастает с N до 2N, то граница времени выполнения возрастает с cNd до c(2N)d = c · 2dNd, что соответствует замедлению с коэффициентом 2d.

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

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

Предлагаемое определение эффективности (3): алгоритм считается эффективным, если он имеет полиномиальное время выполнения.

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

И неполиномиальное время выполнения n1+0,02(log n) покажется нам относительно приемлемым? Конечно, в обоих случаях ответ будет положительным. В самом деле, как бы мы ни старались абстрактно оправдать определение эффективности в контексте полиномиального времени, главное оправдание будет таким: это определение действительно работает.

У задач, для которых существуют алгоритмы с полиномиальным временем, эти алгоритмы почти всегда работают с временем, пропорциональным полиномам с умеренной скоростью роста, такой как n, n log n, n2 или n3.

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

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

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

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