Владстон Феррейра Фило - Теоретический минимум по Computer Science [Все что нужно программисту и разработчику]

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

Чтобы наглядно представить взрывной экспоненциальный рост, уменьшим еще масштаб графика и изменим числа (рис. 2.5). Для экспоненциальной функции основание уменьшено с 2 до 1,5 и добавлен делитель 1000. Степенной же показатель увеличен с 2 до 3 и добавлен множитель 1000.

Рис. 2.5.Никакая степенная функция не превзойдет экспоненциальную. На этом графике выбран такой масштаб, что кривой n log n даже не видно из-за ее слишком медленного роста

Есть еще более бесполезные алгоритмы. Речь идет об алгоритмах с факториальным временем , сложность которых составляет O ( n! ). Алгоритмы с экспоненциальным и факториальным временем ужасны, но они нужны для выполнения самых трудных вычислительных задач — знаменитых недетерминированных полиномиальных ( NP-полных ) задач. Мы увидим примеры NP-полных задач в следующей главе. А пока запомните вот что: первый человек, который найдет неэкспоненциальный алгоритм для NP-полной задачи, получит миллион долларов [27] Было доказано, что неэкспоненциальный алгоритм для любой NP-полной задачи может быть обобщен для всех NP-полных задач. Поскольку мы не знаем, существует ли такой алгоритм, вы также получите миллион долларов, если докажете, что NP-полная задача не может быть решена с использованием неэкспоненциальных алгоритмов. от Математического института Клэя, частной некоммерческой организация, расположенной в Кембридже.

Очень важно распознать класс задачи, с которой вы имеете дело. Если она является NP-полной, то пытаться найти ее оптимальное решение — это все равно что сражаться с ветряными мельницами (если только вы не решили получить тот миллион долларов).

Даже если бы мы могли выполнять операции бесконечно быстро, мы все равно столкнулись бы с ограничениями. Алгоритмам во время их исполнения нужна рабочая область для хранения промежуточных результатов. Эта область занимает память компьютера , отнюдь не бесконечную.

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

Например, для сортировки выбором (см. раздел «Оценка затрат времени») нужна рабочая область хранения для фиксированного набора переменных. Число переменных не зависит от объема входных данных. Поэтому мы говорим, что пространственная сложность сортировки выбором составляет O ( 1 ) — независимо от объема входных данных она требует одного объема памяти компьютера для рабочей области хранения.

Однако многие другие алгоритмы нуждаются в такой рабочей области хранения, которая растет вместе с объемом входных данных. Иногда бывает невозможно удовлетворить потребности алгоритма в памяти. Вы не найдете подходящий алгоритм сортировки с временной сложностью O ( n log n ) и пространственной сложностью O ( 1 ). Ограниченность памяти компьютера иногда вынуждает искать компромисс. В случае если доступно мало памяти, вам, вероятно, потребуется медленный алгоритм с временной сложностью, потому что он имеет пространственную сложность O ( 1 ). В последующих главах мы увидим, как разумно выстроенная обработка данных способна улучшить пространственную сложность.

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