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

Когда аналитики только начали заниматься анализом дискретных алгоритмов (а эта область исследований стала набирать темп в 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.

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

Еще одна причина, по которой математические формальные методы и эмпи- рические данные хорошо сочетаются в случае полиномиальной разрешимости, связана с огромными расхождениями между скоростью роста полиномиальных и экспоненциальных функций. Допустим, имеется процессор, выполняющий миллион высокоуровневых команд в секунду, и алгоритмы с границами времени выполнения n, n log2 n, n2, n3, 1,5n, 2n и n!. В табл. 2.1 приведено время выполнения этих алгоритмов (в секундах, минутах, днях или годах) для входных данных с раз- мером n = 10, 30, 50, 100, 1000, 10 000, 100 000 и 1 000 000.

Таблица 2.1. Время выполнения (с округлением вверх) разных алгоритмов для входных данных разного размера (для процессора, выполняющего миллион высоко уровневых команд в секунду). Если время выполнения алгоритма превышает 1025 лет, мы просто используем пометку «очень долго»



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

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

2.2.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

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

  1. Сейчас наша популяция сократилась до такого уровня, что нам всё труднее обеспечивать защиту Западного Побережья, которую мы до сих пор предоставляли, в то время как в самом близком будущем вам потребуется гораздо более эффективная защита.
  2. КАК ПОВЫСИТЬ ЭФФЕКТИВНОСТЬ СВОИХ ДЕЙСТВИЙ
  3. АВРАЛ КАК ЭФФЕКТИВНЫЙ СПОСОБ ОРГАНИЗАЦИИ РАБОТЫ
  4. Как использовать тип для более эффективного консультирования
  5. В) КАК ДЕЛАТЬ ВРЕМЯ
  6. ГЛАВА 7 КАК МЫ ИСПОЛЬЗУЕМ ВРЕМЯ
  7. ГЛАВА 7 КАК МЫ ИСПОЛЬЗУЕМ ВРЕМЯ
  8. Почему могут возникнуть ссоры между супругами, в то время как их отношения кажутся прочными
  9. Время сейчас такое – время мудрости пришло!
  10. Как вести себя родителям, чтобы сделать своего ребенка счастливым и в то же время не дать ему инфицироваться?
  11. В это время многие люди быстро стареют и слабеют, так как не понимают стоящих перед ними задач.
  12. Дорогой Мастер Крайон, расскажи, пожалуйста, об асанах, йоге, о том, как посредством тела изменить реальность, пространство, время и т.д. и т.п.?
  13. ПОКАЗАТЕЛЬ
  14. АСТРОЛОГИЧЕСКИЕ ПОКАЗАТЕЛИ ПРОФЕССИЙ
  15. Корректировка выборочных показателей.
  16. 14. 4. Рабочее время и время отдыха
  17. ПОКАЗАТЕЛИ САМОУБИЙСТВА