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

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

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

Какие инструкции считать? Ответ на этот вопрос не всегда очевиден, но, по крайней мере, мнения сходятся в одном – при подсчете следует учитывать только существенные операции. К ним обычно относят:

· простое присваивание: а ← b;

· индексация элемента массива (нахождение его значения);

· арифметические операции: -, +, *, /;

· операции сравнения: <, >, =, <=, >=, <>;

· логические операции: or, and, not.

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

Посчитаем число инструкций алгоритма линейного поиска:

В лучшем случае искомому элементу (ключу) равно значение первого элемента массива. Тогда потребуется всего четыре операции:

· в заголовке цикла: присвоение переменной i начального значения и сравнение этого значения со значением n;

· в операторе ветвления: индексация i-ого элемента и сравнение его с ключом.

В худшем случае искомый элемент окажется в конце массива, либо он вовсе будет отсутствовать. В таком случае цикл выполнит n итераций, и число операций возрастет до 2+4n:

· в заголовке цикла: начальное присвоение и первое сравнение, а также nсравнений и n увеличений значения счетчика: 2+2n;

· в операторе ветвления: n индексаций и n сравнений: 2n.

Теперь посчитаем количество инструкций алгоритма нахождения максимального элемента:

В первой строке выполняются две операции: нахождение в массиве A элемента с индексом 0 и присвоение значения этого элемента переменной Max. Перед запуском тела цикла выполняются еще две операции: инициализация переменной счетчика i и сравнение значения этой переменной с числом элементов n. Цикл выполнит n-1 итерацию, за это время i инкрементируется n-1 раз и условие (i<n) проверится n-1 раз. Тело цикло выполнилось n-1 раз, следовательно, оператор ветвления сравнил значения элементов n-1 раз, выполнив тем самым по две инструкции на каждой итерации: нахождение i-ого элемента и сравнение его сMax. Получаем количество операций алгоритма: 2+2+4(n-1) = 4+4n-4 = 4n.

Такой будет сложность алгоритма в лучшем случае, т. е. максимальный элемент соответствовал первому элементу массива, поэтому оператор ветвления в теле цикла не выполнялся. В худшем случае массив будет упорядочен по возрастанию, а значит, на каждой итерации потребуется заменить значение переменной Max. Это потребует еще по две инструкции на каждой итерации: нахождения i-ого элемента и присвоения его значения переменной Max. В итоге получим количество операций для наихудшего случая: 4n+2n=6n.