Лекция 3 Оценка сложности алгоритмов.

Методы анализа алгоритмов (3 часа)

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

Математический аппарат анализа алгоритмов

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

 

Алгоритм — это точное предписание, однозначно определяющее вычислительный процесс, ведущий от варьируемых начальных данных к искомому результату [1].

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

Модель RAM (Random Access Machine)

Каждое вычислительное устройство имеет свои особенности, которые могут влиять на длительность вычисления. Обычно при разработке алгоритма не берутся во внимание такие детали, как размер кэша процессора или тип многозадачности, реализуемый операционной системой. Анализ алгоритмов проводят на модели абстрактного вычислителя, называемого машиной с произвольным доступом к памяти (RAM).

Модель состоит из памяти и процессора, которые работают следующим образом:

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

Несмотря на то, что такая модель далека от реального компьютера, она замечательно подходит для анализа алгоритмов. После того, как алгоритм будет реализован для конкретной ЭВМ, вы можете заняться профилированием и низкоуровневой оптимизацией, но это будет уже оптимизация кода, а не алгоритма.

Подсчет операций. Классы входных данных

Одним из способов оценки трудоемкости (Tn) является подсчет количества выполняемых операций. Рассмотрим в качестве примера алгоритм поиска минимального элемента массива.

1. начало; поиск минимального элемента массива array из N элементов

2. min:= array[1]

3. для i от 2 до N выполнять:

4. если array[i] < min

5. min:= array[i]

6. конец; вернуть min

При выполнении этого алгоритма будет выполнена:

1. N — 1 операция присваивания счетчику цикла i нового значения;
2. N — 1 операция сравнения счетчика со значением N;
3. N — 1 операция сравнения элемента массива со значением min;
4. от 1 до N операций присваивания значения переменной min.

Точное количество операций будет зависеть от обрабатываемых данных, поэтому имеет смысл говорить о наилучшем, наихудшем и среднем случаях. При этом худшему случаю всегда уделяется особое внимание, в том числе потому, что «плохие» данные могут быть намеренно поданы на вход злоумышленником.

Понятие среднего случая используется для оценки поведения алгоритма с расчетом на то, что наборы данных равновероятны. Однако, такая оценка достаточно сложна:

1. исходные данные разбиваются на группы так, что трудоемкость алгоритма (ti) для любого набора данных одной группы одинакова;
2. исходя из доли наборов данных группы в общем числе наборов, рассчитывается вероятность для каждой группы (pi);
3. оценка среднего случая вычисляется по формуле: ∑i=1mpi⋅ti.

Асимптотические обозначения

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

При анализе скорости роста игнорируются постоянные члены и множители в выражении, т.е. функции fx=10⋅x2+20 и gx=x2 эквивалентны с точки зрения скорости роста. Незначащие члены лишь добавляют «волнистости», которая затрудняет анализ.

В оценке алгоритмов используются специальные асимптотические обозначения, задающие следующие классы функций:

• O(g) — функции, растущие медленнее чем g;
• Ω(g) — функции, растущие быстрее чем g;
• Θ(g) — функции, растущие с той же скоростью, что и g.

Запись fn=O(gn) означает принадлежность функции f классу O(g), т.е. функция f ограничена сверху функцией g для достаточно больших значений аргумента. ∃n0>0,c>0:∀n>n0,fn≤c⋅gn.

Ограниченность функции g снизу функцией f записывается следующим образом: gn=Ω(fn). Нотации Ω и O взаимозаменяемы: fn=O(gn)⇔gn=Ω(fn).

Асимптотические обозначения «О большое» и «Омега большое»

Если функции f и g имеют одинаковую скорость роста (fn=Θ(gn)), то существуют положительные константы c1 и c2 такие, что ∃n0>0:∀n>n0,fn≤c1⋅gn,fn≥c2⋅gn. При этом fn=Θ(gn)⇔gn=Θ(fn).

Асимптотическое обозначение «Тета большое»

Примеры анализа алгоритмов

Алгоритм поиска минимального элемента массива, приведенный выше, выполнит N итераций цикла. Трудоемкость каждой итерации не зависит от количества элементов массива, поэтому имеет сложность Titer=O(1). В связи с этим, верхняя оценка всего алгоритма Tminn=O(n)⋅O(1)=O(n⋅1)=O(n). Аналогично вычисляется нижняя оценка сложности, а в силу того, что она совпадает с верхней — можно утверждать Tminn=Θ(n).

Алгоритм пузырьковой сортировки (bubble sort) использует два вложенных цикла. Во внутреннем последовательно сравниваются пары элементов и если оказывается, что элементы стоят в неправильном порядке — выполняется перестановка. Внешний цикл выполняется до тех пор, пока в массиве найдется хоть одна пара элементов, нарушающих требуемый порядок [2].

1. 1. начало; пузырьковая сортировка массива array из N элементов

2. 2. nPairs:= N; количество пар элементов

3. 3. hasSwapped:= false; пока что ни одна пара не нарушила порядок

4. 4. для всех i от 1 до nPairs-1 выполнять:

5. 5. если array[i] > array[i+1] то:

6. 6. swap(array[i], array[i+1]); обменять элементы местами

7. 7. hasSwapped:= true; найдена перестановка

8. 8. nPairs:= nPairs - 1; наибольший элемент гарантированно помещен в конец

9. 9. если hasSwapped = true - то перейти на п.3

10. 10. конец; массив array отсортирован

Трудоемкость функции swap не зависит от количества элементов в массиве, поэтому оценивается как Tswap=Θ(1). В результате выполнения внутреннего цикла, наибольший элемент смещается в конец массива неупорядоченной части, поэтому через N таких вызовов массив в любом случае окажется отсортирован. Если же массив отсортирован, то внутренний цикл будет выполнен лишь один раз.

Таким образом:

• Tbubblen=O(∑i=1n∑j=1n−i1)=O(∑i=1nn)=O(n2);
• Tbubblen=Ω(1⋅∑j=1n−i1)=Ω(n).

В алгоритме сортировки выбором массив мысленно разделяется на упорядоченную и необработанную части. На каждом шаге из неупорядоченной части массива выбирается минимальный элемент и добавляется в отсортированную часть [2].

1. начало; selection_sort - сортировка массива array из N элементов методом выбора

2. для всех i от 1 до N выполнять:

3. imin:= indMin(array, N, i)

4. swap(array[i], array[imin])

5. конец; массив array отсортирован

Для поиска наименьшего элемента неупорядоченной части массива используется функция indMin, принимающая массив, размер массива и номер позиции, начиная с которой нужно производить поиск. Анализ сложности этой функции можно выполнить аналогично тому, как это сделано для функции min — количество операций линейно зависит от количества обрабатываемых элементов: TindMinn,i=Θ(n—i).

У сортировки выбором нет ветвлений, которые могут внести различия в оценку наилучшего и наихудшего случаев, ее трудоемкость: Tselectn=Θ(∑i=1n(TindMinn,i+Tswap))=Θ(∑i=1n(n−i))=Θ(n−12⋅n)=Θ(n2).