Способы перехода
Для данного критерия определения эффективности существуют два основных способа перехода от заданного алгоритма к более эффективному. Первый из них состоит в том, чтобы, сохранив основную идею алгоритма, попытаться извлечь из него лучшее при помощи оптимизации его частей или совершенствования способа реализации. Такой путь рассматривается в разд. 3.3 с точки зрения основных ресурсов ЭВМ — времени и памяти, поэтому здесь мы на нем останавливаться не будем Второй способ заключается в разработке совершенно другого алгоритма. Для иллюстрации рассмотрим два алгоритма суммирования первых IV натуральных чисел.
В алгоритме А по мере возрастания IV итеративный процесс все удлиняется и удлиняется. В алгоритме В процесс занимает одинаковое время для любого N, с той лишь оговоркой, что для обработки большего числа потребуется чуть больше времени (человеку, но не машине, которая имеет постоянное время выполнения операций). Очевидно, что алгоритм В более эффективный, за исключением, может быть, случаев, когда 7V очень мало и практически можно сказать, что алгоритм эффективен в абсолютном смысле. Однако разработчик алгоритмов, незнакомый с приведенной формулой, может никогда ее не вsdести. Несколько менее тривиальный случай — машинный алгоритм для численного интегрирования некоторой функции, проинтегрировав которую аналитически, математик мог бы вывести формулу, по которой непосредственно можно получить требуемый результат.
Эти примеры показывают, что не следует использовать первый пришедший на ум алгоритм, не рассмотрев альтернативных вариантов, и что нахождение наилучшего (из известных) алгоритмов для данной задачи нередко требует специальных знаний в области приложения алгоритма. Это еще раз подтверждает сказанное в предыдущем разделе о необходимости пользоваться соответствующей литературой.
Второй критерий — универсальное т ь, т. е. способность алгоритма решать широкий класс задач. Как правило, первоначально алгоритм разрабатывается для решения одной конкретной задачи, но часто имеется возможность рассмотреть эту задачу как частный случай некоторого более общего процесса. Очевидным преимуществом такого подхода является то, что алгоритм будет иметь широкую область приложения. Однако существуют и другие достоинства — проектирование более универсального алгоритма обычно требует углубленной проработки задачи, поэтому, концентрируя внимание на bх сходстве, а не на различиях, можно решить целый класс задач, которые с первого взгляда казались не связанными.
Обобщение алгоритма иногда может достигаться при помощи тривиального изменения: все, что требуется в таких случаях, это подставить вместо константы переменную. Рассмотрим, например, задачу подсчета числа слов на странице текста. Ядро алгоритма, решающего эту задачу (хотя само по себе оно не могло бы решить весь класс подобных задач), могло бы состоять из увеличения счетчика на единицу при каждом встреченном пробеле. Изменяя символ, который вызывает приращение счетчика, и задавая в качестве параметра алгоритма символ точка, можно было бы по этому алгоритму подсчитывать число предложений в тексте. В данном случае конкретная задача подсчета слов была рассмотрена как Пример более общей задачи поиска разделителей (пробелов, точек, запятых) и выполнения соответствующих действий при их обнаружении.