Анализ алгоритма и его сложности

Анализ алгоритма и его сложности всегда связан с таким понятием как эффективность.

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

Существует ряд важных практических причин для анализа алго­ритмов. Одной из них является необходимость получения оценок или границ для объема памяти, или времени работы, которое потребуется алгоритму для успешной обработки конкретных данных. Машинное время и память — относительно дефицитные (и дорогие) ресурсы, на которые часто одновременно претендуют многие пользователи. Всегда следует избегать прогонов программы, отвергаемых системой из-за нехватки запрошенного времени, которое указывается на рабо­чей карте. Поразительно, скольким программистам приходится слиш­ком дорогим способом выяснять, что их программа не может обрабо­тать входные данные раньше, чем через несколько дней машинного времени. Лучше было бы предугадать такие случаи с помощью каран­даша и бумаги для того, чтобы избежать ненужных прогонов. Хоро­ший анализ способен выявить узкие места в наших программах, т. е. разделы программы, на которые расходуется большая часть времени.

Существуют также важные теоретические причины для анализа алгоритмов. Хотелось бы иметь некий количественный критерий для сравнения двух алгоритмов, претендующих на решение одной и той же задачи. Более слабый алгоритм должен быть улучшен или отброшен. Желательно также иметь механизм для выявления наиболее эффек­тивных алгоритмов и замены устаревших. Иногда невозможно соста­вить четкое мнение об относительной эффективности двух алгоритмов. Один может в среднем лучше работать, к примеру, на случайных входных данных, в то время как другой лучше работает на каких-то специальных входных данных. Хотелось бы иметь возможность де­лать аналогичные выводы о сравнительных достоинствах двух алго­ритмов.

Важно также установить абсолютный критерий. Когда можно считать решение задачи оптимальным? Иными словами, когда алгоритм настолько хорош, что невозможно (независимо от умственных способностей) значительно его улучшить?

С этой целью проведем математические соображения эффективности алгоритма по скорости и памяти.

Пусть А — алгоритм для решения некоторого класса задач, а n — размерность отдельной задачи из этого класса. Во многих задачах этого методического пособия n — просто скаляр, равный числу вершин графа. В об­щем случае n может быть массивом или длиной вводимой последова­тельности. Определим fa(n) как рабочую функцию, дающую верхнюю границу для максимального числа основных операций (сложения, сравнения и т. д.), которые должен выполнить алгоритм А для реше­ния любой задачи размерности n. Или, другими словами, fa(n) - это вектор, компонентами которого являются количество, с одной стороны: времена операций сложения, умножения, сравнения и т.п., использующихся в математическом описании алгоритма, и, с другой стороны, количество времен операций «программистских» индексирование, циклирование и т.п. Для получения численного значения функции fa(n) надо просуммировать компоненты вектора.

Будем пользоваться следующим критерием для оценки качества алгоритма: чем меньше растет функция fa(n) на каком-то участке области n, тем алгоритм будет более эффективным.

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

Поэтому сделаем общее утверждение: необходимо стремиться к тому, чтобы рост алгоритма был как можно меньше от n на той области участка n, на котором требуется получить решение.

К этим общим рассуждениям сделаем одно замечание.

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

Пример. Рассмотрим ранее описанный алгоритм ETS. Сразу можно сделать вывод, что это экспоненциальный алгоритм с оценкой, по крайней мере F(n!).В задаче с n городами алгоритм ЕTS требует от нас исчерпывающе перечислить перестановки первых n-1 положи­тельных целых чисел. Число таких перестановок (n-1)!. Даже если требуется только один шаг для каждой такой перестановки, эта часть алгоритма все же потребует F(n—1)! шагов. Как только представлена перестановка, как в шаге 1 алгоритма ETS, можно найти соответствующий тур и его стоимость за F(n). Поэтому любая верхняя граница для общего времени работы должна быть, по крайней мере, F(n!).

Предположим, что у нашего коммивояжера 20 городов, и что у нас есть феноменальный подалгоритм алгоритма ETS для шага 1, кото­рый генерирует новую перестановку только за один шаг. Предполо­жим также, что мы имеем быстродействующую машину, которая вы­полняет каждый элементарный шаг (например, сравнение, сложение, поиск элемента матрицы) за 10^-7 с. Тогда, так как 20! это примерно 2• 10¹⁸с, реше­ние нашей задачи с использованием алгоритма ЕTS займет немногим меньше 70 веков.

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

Именно теперь уместно подчеркнуть, что к этапам, перечислен­ным в начале главы, не нужно относиться как к чему-то незыбле­мому. Скорее, они представляют собой руководящие принципы. Не­которые шаги могут выполняться одновременно с другими, некото­рые могут быть даже пропущены. Если есть хорошая модель, то, вероятно, нет необходимости строить другую. Порядок шагов не стоит считать раз и навсегда заданным. Конечно, нельзя доказать правиль­ность алгоритма до того, как он разработан, но, может быть, лучше провести некоторый анализ процесса разработки алгоритма прежде, чем его реализовывать. Это тем более так, если есть повод предполо­жить, что алгоритм будет экспоненциальным (как в нашем примере). Некий анализ на стадии разработки может подсказать, как сделать алгоритм более эффективным. И наконец, этапы процесса построения могут быть с выгодой пересмотрены после того, как они уже считаются завершенными. Например, фазы анализа и проверки могут обеспечить ценную обратную связь с этанами разработки и реализации.

Получение для заданного алгоритма функции типа «верхняя гра­ница» в худшем случае попадает под рубрику «анализ алгоритма». Интересно также исследовать все возможные алгоритмы, решающие тот же тип задач, и определить, какой из них лучше относительно данного критерия. Такой анализ очень труден и подпадает под рубрику «сложность вычислений».

Дата добавления: 2014-12-16