Об экспоненциальном росте, полиномиальных алгоритмах и законе Мура

От Сиссы до Мура

Легенда говорит, что брамин Сисса, придумав шахматы, показал их начальству (королю) –– которое игру одобрило и предложило выбрать награду. Брамин скромно попросил положить одну рисинку на первую клетку доски, две – на вторую, четыре – на третью и так далее, удваивая количество вплоть до шестьдесят четвёртой клетки. Король неосторожно согласился и вошёл в историю как первая жертва экспоненциального роста («комбинаторного взрыва»): запрошенное количество риса,

2^64 -1 = 18 446 744 073 709 551 615

зёрен, в тысячи раз превосходит годовой урожай риса во всей Индии! Это не просто байки: скажем, бактерии (при отсутствии ограничений) тоже размножаются экспоненциально. В 1798 году английский философ Томас Роберт Мальтус предсказал, в современных терминах, что экспоненциально растущее (он называл это «геометрическим ростом») население неизбежно сталкивается с полиномиально ограниченными ресурсами (идея, позже повлиявшая на Дарвина).

В 1965 году Гордон Мур, один из первых разработчиков микросхем, заметил, что количество транзисторов в микросхеме в 60-х годах удваивалось примерно каждый год. Мур предположил, что так и будет продолжаться. Сейчас «закон Мура» обычно формулируют так: быстродействие компьютера удваивается каждые 18 месяцев. И действительно, это происходит уже лет сорок – и наряду с разработкой эффективных алгоритмов стало основой стремительного развития информационных технологий.

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

Для примера рассмотрим алгоритм, решающий задачу выполнимости за время O(2^n). В 1975 году такой алгоритм за час мог бы решить задачу для 25 переменных, в 1983 – для 31, в 1995 – для 38. Наконец, на современных компьютерах этот алгоритм за час смог бы обрабатывать формулы с 45 переменными. Прогресс налицо, да только появление новой переменной (удвоение числа операций) требует полутора лет ожидания, а размеры формул в приложениях (в том числе используемых при разработке процессоров) растут гораздо быстрее.

А вот для алгоритма с асимптотикой O(n) или O(n log n) допустимый размер входов увеличивается примерно в 100 раз каждые 10 лет, для алгоритма со временем работы O(n^2) – в 10 раз. Даже не особо эффективный алгоритм с оценкой O(n^6) позволит за это время удвоить размер решаемых задач. Можно сказать так: экспоненциальный рост скорости процессоров приводит к полиномиальному росту размера задач в случае экспоненциальных алгоритмов, и к экспоненциальному росту размера задач для полиномиальных алгоритмов. Так что воспользоваться законом Мура мы смогли именно благодаря эффективным алгоритмам.

Как понимали и Сисса, и Мальтус, и Мур, экспоненциальному росту рано или поздно приходит конец – бактерии останутся без еды, а микросхемы упрутся в атомный масштаб, закону Мура осталось десять или двадцать лет. Дальше будут нужны новые алгоритмы или же совсем новые идеи – скажем, квантовые вычисления, о которых пойдёт речь в главе 10.

По книге Дасгупта С., Пападимитриу Х., Вазирани У. «Алгоритмы»

Источник: m.vk.com

Комментарии: