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

Next:3.6 Кодирование алгоритма (программирование)
Up:3 Общие рекомендации по выполнению заданий
Previous:3.4 Обоснование алгоритма

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

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

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

Т а б л и ц а 1

Т а б л и ц а 2

Хорошим критерием качества алгоритма является скорость роста его сложности в зависимости от увеличения размера входа. Рассмотрим пример, показывающий влияние порядка роста сложности алгоритма на увеличение максимально допустимого размера входных данных, которого можно достичь увеличением скорости ЭВМ, а также эффект применения более эффективного алгоритма (см. табл. 1 и 2). Из табл. 1 видно, что может обработать за 1 с входные данные размером 1000, в то время как -- входные данные не длиннее 9. Табл. 2 показывает, что для алгоритма десятикратное увеличение скорости ЭВМ позволяет увеличить размер входных данных, к которым его можно применять, только на три, тогда как для алгоритма размер входных данных можно по крайней мере утроить.

Следует, однако, иметь в виду, что порядок роста сложности алгоритма является определяющим только при обработке данных большого размера. Для задач с малым размером входных данных (а именно на таких данных и проверяется правильность студенческих алгоритмов) следует учитывать мультипликативные константы при сравнении алгоритмов. Например, предположим, что временные сложности алгоритмов и равны соответственно , $100n \log n$ , . Тогда будет наилучшим для данных размером $2 \leq n \leq 9,A_3$ -- для данных размером $10 \leq n \leq 58, A_2$ -- при $59 \leq n \leq 1024$ , а -- только при .

В качестве примера приведем анализ временной сложности двух алгоритмов генерации перестановок из п. 4.11.

Общую эффективность алгоритма генерации перестановок в лексикографическом порядке определяют две операции -- число транспозиций и число сравнений пар элементов в перестановке. Обозначим через и соответственно число транспозиций и число сравнений, выполняемых алгоритмом для порождения первых из перестановок. Поскольку для порождения каждой из подпоследовательностей перестановок с одним и тем же значением $\pi_1$ требуется $I_{n-1}$ транспозиций, а для каждого из переходов от одной подпоследовательности к другой требуется транспозиций, получаем следующее рекуррентное соотношение:

для решения этого рекуррентного соотношения сделаем замену переменных. Взяв $S_n = I_n \frac{n+1}{2}$ , получим новое рекуррентное соотношение:

Решение этого соотношения легко получить:

Поэтому

Аналогично можно показать, что

и получить

Что же касается алгоритма порождения перестановок в порядке минимального изменения, то он выполняет транспозиций и сравнений (более точно, алгоритм делает 1!+2!+3!+...+ n! сравнений). Таким образом, алгоритм порождения перестановок в порядке минимального изменения является более эффективным.

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

Как правило, более эффективный алгоритм приводит к программе большего размера и требует больших усилий как на его разработку, так и на его обоснование.