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

Оценка корректности алгоритма

После представления алгоритма в какой-либо форме, необходимо оценить его корректность. Это означает, что вы должны доказать, что выбран­ный алгоритм за ограниченный промежуток времени выдает требуемый результат для любых корректных значений входных данных. Например, корректность алго­ритма Евклида для вычисления НОД двух чисел, тип, следует из правильности равенства gcd (т, n) = gcd (n, m mod n), которое, в свою очередь, должно быть доказано, а также из простого наблюдения, что второе чис­ло на каждой итерации будет все время уменьшаться, и по достижении им нуля, выполнение алгоритма прекращается.

Доказать корректность одних алгоритмов очень легко, других — невероятно сложно. Универсальным методом доказательства корректности алгоритма считает­ся метод математической индукции. Дело в том, что алгоритмы по своей природе являются итеративными и описываются в виде последовательности пошаговых инструкций, которые как раз и используются при доказательстве методом индук­ции. Стоит отметить, что, хотя отслеживание быстродействия алгоритма с по­мощью нескольких наборов тщательно подобранных входных данных приводит к очень полезным результатам, подобную проверку нельзя считать убедительной при доказательстве корректности алгоритма. Однако доказательством некоррект­ной работы алгоритма может служить лишь один набор входных данных, при обработке которых получается неправильный результат. Если некорректная ра­бота алгоритма будет доказана, придется либо несколько видоизменить его, не выходя за рамки принятых структур данных, методов проектирования и т.п., ли­бо решать проблему более кардинально, пересмотрев принятые ранее принципы и подходы.

Обычно создатели алгоритмов стараются, чтобы они удовлетворяли несколь­ким требованиям. После проверки корректности алгоритма одной из самых важ­ных характеристик является оценка его эффективности. На практике существует два вида оценки эффективности алгоритма: временная и пространственная. Вре­менная эффективность (time efficiency) является индикатором скорости работы алгоритма. Что касается пространственной эффективности (space efficiency), то эта оценка показывает количество дополнительной оперативной памяти, необ­ходимой для работы алгоритма.

Еще одной важной характеристикой алгоритма является его простота (sim­plicity). В отличие от эффективности, которую можно точно определить и оце­нить с помощью строгих математических выражений, простота алгоритма чем-то напоминает человеческую красоту, понятие которой настолько субъективно, что выработать объективные критерии ее оценки весьма непросто. Например, боль­шинство людей считают, что алгоритм Евклида поиска НОД двух чисел проще, чем тот, которому нас учили в школе, но это вовсе не означает, что он понятнее. В то же время алгоритм Евклида проще алгоритма последовательного перебора целых чисел. Тем не менее простота является важной характеристикой алгорит­ма, и к ней нужно стремиться. Вы спросите, почему? Дело в том, что простые алгоритмы легче понять и запрограммировать. Следовательно, в полученной про­грамме будет содержаться меньше ошибок. Кроме того, в простоте существует неоспоримая эстетическая привлекательность. Ну и наконец, простые алгоритмы зачастую более эффективны, чем их сложные аналоги. К сожалению, последнее утверждение не всегда выполняется. В подобных случаях необходимо руковод­ствоваться здравым смыслом и принимать компромиссные решения.

Следующей важной характеристикой алгоритма является его общность, или универсальность (generality). По сути, здесь можно выделить два момента: общ­ность задачи, для решения которой разработан алгоритм, и диапазон допустимых значений его входных данных. По поводу первого замечания следует сказать, что иногда легче разработать алгоритм для решения общей задачи, чем заниматься поиском решения ее частного случая. В качестве примера рассмотрим такую за­дачу: определить, являются ли два целых числа взаимно простыми. Напомним, что два числа считаются взаимно простыми, если у них нет общих делителей, кроме 1. В данном случае легче разработать алгоритм для решения общей задачи вычисления НОД двух целых чисел. Затем, чтобы решить исходную задачу, достаточно подставить заданные числа в функцию gcd и проверить, равно ли ее значение 1. Однако бывают случаи, когда разработка более общего алгоритма нежелательна, затруднена или даже невозможна. Например, излишне выполнять сортировку всего списка, содержащего п чисел, чтобы определить их медиану, поскольку достаточно просто найти значение лг-го наименьшего элемента, где т = \п/2]. Еще один пример: известно, что стандартную формулу для поиска корней квадратного уравнения нельзя обобщить для поиска корней полиномов более высоких степеней.

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

Если вас не устраивает эффективность, простота или общность алгоритма, придется снова взять в руки карандаш и перепроектировать алгоритм. И даже если анализ алгоритма привел к положительным результатам, имеет смысл по­искать другое алгоритмическое решение задачи. Достаточно вспомнить три алго­ритма определения НОД, рассмотренных в предыдущем разделе. Вообще говоря, не стоит надеяться, что вы с первой попытки найдете оптимальное решение за­дачи. Самое меньшее, что можно сделать, попытаться оптимизировать созданный алгоритм. Всегда помните высказывание Антуана де Сент-Экзюпери (Antoine de Saint-Exupery), известного французского писате­ля, летчика и авиаконструктора: "Конструктор достигает совершенства не тогда, когда ему больше нечего добавить к своему детищу, а тогда, когда больше ничего удалить".

Дата добавления: 2017-01-13