Анализ алгоритмов

Как бы тщательно не разрабатывался алгоритм, он должен быть подвергнут всестороннему анализу. Этот анализ предполагает доказательство правильности (корректности) алгоритма и определение его временных характеристик, т.е. установление того, как быстро алгоритм решает задачу.

Определение 5.3. Под правильностью алгоритма понимают то, что он правильно решает задачу.

На практике доказательство правильности алгоритма ведется двумя путями: теоретически и экспериментально. Однако ни один из этих путей не является исчерпывающим. Наиболее убедительным считается применение обоих методов.

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

Пусть W — множество перестановок п целых чисел мощностью п. На W задан функционал /(л), отображающий каждую перестановку л е W в действительное положительное число d е R+ ограниченного множества R+ действительных чисел. Требуется найти перестановку п е W, доставляющую наименьшее значение функционалу /(л).

Самым общим методом решения этой задачи является перечисление всех п перестановок и фиксация той перестановки л е W, для которой /(л*) = min/(л).

neW

Такой метод поиска называется методом прямого перебора. Убедимся в том, что алгоритм прямого перебора правильный.

Алгоритм начинает работу с выделения некоторой первой перестановки л, е W и вычисления значения /(л,). Далее он действует так, что выделяет очередную перестановку л2 е W и вычисляет /(л2). Сравнивая /(л,) с /(л2), алгоритм запоминает ту из перестановок л,, л2, для которой /(л) имеет меньшее или равное значение. Другую перестановку он забывает и уменьшает число просмотренных перестановок на единицу. Далее действия алгоритма повторяются. Поскольку число перестановок конечно, их просмотр, сравнение функционалов и выделение лучшей перестановки будет доведено до конца. При этом перестановка л*, доставляющая /(л), не будет пропущена. Следовательно, она будет найдена и запомнена.

Для доказательства правильности более сложных алгоритмов авторы работы [ 17] предполагают использовать методику, которая состоит в последовательном доказательстве правильности каждого шага алгоритма с последующим доказательством конечности его шагов.

Самая распространенная процедура экспериментального доказательства правильности алгоритма — прогон программы на разных, заранее заготовленных ручным способом тестах (контрольных примерах). Эти тесты должны предусматривать проверку всех ветвей программы, что для сложных алгоритмов выполнить не так просто. Поэтому всегда существует вероятность того, что некоторая ветвь не будет проверена и при определенной структуре исходных данных программа даст неверный ответ.

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

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

Оба указанных метода анализа алгоритмов опираются на следующие соображения. Полагают, что на вход любого алгоритма поступает некоторый объем данных, которые он преобразует в результаты решения задачи. Этот объем трактуется как переменная величина, зависящая от размера задачи. Для задач на графах это может быть число его вершин или ребер; для задач теории расписаний — число операций, которые должны выполнить процессоры; для задачи о путешествующем торговце (коммивояжере) — число городов, которые он должен посетить и т. п.

Таким образом, время решения задачи тем или иным алгоритмом связывается с объемом данных на его входе, и временной характеристикой алгоритма становится функция времени, определенная на всевозможных размерах входа.

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

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

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

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

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

Методы теоретического анализа временных характеристик алгоритмов (временной их сложности) не используют параметр времени работы алгоритма в явном виде. Вместо него рассматривается суммарное количество основных операций (сравнений, сложений, умножений и т.п.), которые выполняет алгоритм на различных по размеру наборах данных его входа в худшем, среднем и лучшем случаях. Таким способом, с одной стороны, осуществляется переход к количественному параметру алгоритма, значение которого можно подсчитать, с другой — в поле зрения оставляется время работы программы, поскольку оно пропорционально зависит от количества основных операций, которые она выполняет.

Для связи суммарного количества операций, выполняемых рассматриваемым алгоритмом с размером задачи п, используется функция /(л), которая возвращает верхнюю границу максимального числа операций при данном размере п. Функциональная зависимость /(п) асимптотически, т. е. при п —»°°, оценивается сверху, для чего используется известная функция g(n).

Говорят, что функция /(п) при увеличении п растет также бы-

стро, как и g(n), но не быстрее ее, если предел отношения

/(«)

g(n)

при п —> °° равен константе и не равен нулю. Последнее записывают как lim = const ф 0. В том случае, когда lim ^ = 1, функ-

п —> °°

g(n) g(n)

ция /(п) асимптотически равна функции g(ri).

Сравнение скорости роста функций дает возможность грубо (на уровне порядка максимального количества основных операций) оценивать и сравнивать разные алгоритмы. Например, если

2” исследуются алгоритмы, для которых f(ri) = — - 100, f{n)-n и

f(ri) = 3,7л2 +100,8л + 106, то lim

Т_

  • 100
  • -100
  • 2"

= 0,01 = const ф 0, так

2" 100 A m 100

как -!-^ = 0,01, а —— очень малое число, которым можно пре-— —

небречь.

Для оценки скорости роста функции f(n) - п выберем функ-

п

цию g(n) = пп. Тогда lim—L = lim

п—>оо — Л »1 —

(п -1 )п

п

И->оо п" 1 п

=... = 1 = const ф 0. Для

оценки скорости роста третьей функции f(n) примем g(n) = п2.

п 3,7л2+100,8/7+ 106

Применяя предельный переход, получим lim---=

/ 7 —> °о

= 3,7 = const ф 0.

Таким образом, временные сложности алгоритмов с заданными зависимостями основных количеств операций от размера входа алгоритма соответственно 0(2"), 0(л"), 0(п2).

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

 
< Пред   СОДЕРЖАНИЕ     След >