Полиномиальное время как показатель эффективности
На математическом уровне эта закономерность масштабироваться может быть сформулирована так. Предположим, алгоритм обладает следующим свой- ством: существуют такие абсолютные константы 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.
Еще по теме Полиномиальное время как показатель эффективности:
- Сейчас наша популяция сократилась до такого уровня, что нам всё труднее обеспечивать защиту Западного Побережья, которую мы до сих пор предоставляли, в то время как в самом близком будущем вам потребуется гораздо более эффективная защита.
- КАК ПОВЫСИТЬ ЭФФЕКТИВНОСТЬ СВОИХ ДЕЙСТВИЙ
- АВРАЛ КАК ЭФФЕКТИВНЫЙ СПОСОБ ОРГАНИЗАЦИИ РАБОТЫ
- Как использовать тип для более эффективного консультирования
- В) КАК ДЕЛАТЬ ВРЕМЯ
- ГЛАВА 7 КАК МЫ ИСПОЛЬЗУЕМ ВРЕМЯ
- ГЛАВА 7 КАК МЫ ИСПОЛЬЗУЕМ ВРЕМЯ
- Почему могут возникнуть ссоры между супругами, в то время как их отношения кажутся прочными
- Время сейчас такое – время мудрости пришло!
- Как вести себя родителям, чтобы сделать своего ребенка счастливым и в то же время не дать ему инфицироваться?
- В это время многие люди быстро стареют и слабеют, так как не понимают стоящих перед ними задач.
- Дорогой Мастер Крайон, расскажи, пожалуйста, об асанах, йоге, о том, как посредством тела изменить реальность, пространство, время и т.д. и т.п.?
- ПОКАЗАТЕЛЬ
- АСТРОЛОГИЧЕСКИЕ ПОКАЗАТЕЛИ ПРОФЕССИЙ
- Корректировка выборочных показателей.
- 14. 4. Рабочее время и время отдыха
- ПОКАЗАТЕЛИ САМОУБИЙСТВА