Задача оценки и выбора алгоритмов

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

· точность решения задачи

· затраты машинного времени

· затраты оперативной памяти

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

· минимально возможное число повторов элементарных операций в наилучшем случае

· среднее число повторов

· максимальное число повторов для наихудшего случая

Например, в задаче поиска в неупорядоченном массиве или списке из n элементов базовой операцией является сравнение заданного значения с ключом элемента массива. Тогда минимальное число сравнений равно 1 (совпадение произошло на первом элементе массива), максимальное равно n (просмотрен весь массив), а среднее - около n/2.

В отличие от этого, двоичный поиск в упорядоченном массиве или в “хорошем” двоичном дереве поиска дает другие оценки: минимум – 1, максимум - log ₂ n, среднее – 0,5* (log ₂ n).

Получение подобных оценок часто является сложной математической задачей. Наиболее полный анализ методов получения этих оценок для всех основных алгоритмов приводится в фундаментальной многотомной работе Дональда Кнута [1, 2].

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

Для оценивания трудоемкости алгоритмов была введена специальная система обозначений – так называемая О-нотация. Эта нотация позволяет учитывать в функции f (n) лишь наиболее значимые элементы, отбрасывая второстепенные.

Например, в функции f (n) = 2n² + n – 5 при достаточно больших n компонента n² будет значительно превосходить остальные слагаемые, и поэтому характерное поведение этой функции определяется именно этой компонентой. Остальные компоненты можно отбросить и условно записать, что данная функция имеет оценку поведения (в смысле скорости роста ее значений) вида О(n² ).

Аналогично, для функции f (n) = 2ⁿ + 3n³ – 10 начиная с некоторого n первое слагаемое будет превосходить второе и поэтому данную функцию можно описать оценкой О(2ⁿ).

Важность О-оценивания состоит в том, что оно позволяет описывать характер поведения функции f(n) с ростом n: насколько быстро или медленно растет эта функция.

О-оценка позволяет разбить все основные функции на ряд групп в зависимости от скорости их роста:

1. постоянные функции типа О(1), которые с ростом n НЕ растут (в оценивании алгоритмов этот случай встречается крайне редко, но все-таки встречается!)

2. функции с логарифмической скоростью роста О(log ₂ n)

3. функции с линейной скоростью роста О(n)

4. функции с линейно–логарифмической скоростью роста О(n*log ₂ n)

5. функции с квадратичной скоростью роста О(n² )

6. функции со степенной скоростью роста О(n^a) при а>2

7. функции с показательной или экспоненциальной скоростью роста О(2ⁿ)

8. функции с факториальной степенью роста О(n!)

В этом списке функции упорядочены именно по критерию скорости роста: сначала идут медленно растущие функции, потом – все более быстро растущие. Графики некоторых функций приведены на рисунке.

Отсюда можно сделать несколько выводов.

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

2. Если заранее известно, что размерность решаемых задач невелика, но зато число их повторений очень большое, имеет смысл рассмотреть возможность использования алгоритмов не с самой лучшей оценкой, поскольку при малых n “лучшие” алгоритмы могут вести себя хуже, чем “плохие” (это можно заметить по графику в области начала координат)

3. Алгоритмы класса О(2ⁿ) и О(n!) следует использовать с большой осторожностью, учитывая катастрофический рост их трудоемкости уже при n>100. Например, если число базовых операций определяется соотношением 2ⁿ, то при n=100 это число будет примерно равно 10³⁰, и если одна базовая операция выполняется за 1 микросекунду, то это потребует около 10²⁴ секунд, т.е. порядка 10¹⁶ лет. К сожалению, задачи с подобной трудоемкостью довольно часто встречаются на практике и их точное решение пока невозможно даже на сверхбыстрых суперкомпьютерах!

Как быть с оценкой трудоемкости программы в целом, если в программе используется несколько алгоритмов, решающих свои конкретные задачи? Есть два основных способа взаимодействия алгоритмов – последовательное и вложенное. При последовательном выполнении алгоритмов с оценками O(f1), O(f2), …, O(fk) общая трудоемкость определяется трудоемкостью алгоритма с максимальным значением:

O (программы) = Max (O(f1), O(f2), . . ., O(fk))

При вложенном выполнении общая трудоемкость есть произведение оценок вложенных друг в друга алгоритмов: O(программы) = O(f1)*O(f2)*O(f3)