Асимптотические характеристики

Алгоритмы и структуры данных

Структура курса

6 часов лекций, 12 часов лабораторных работ, 1 контрольная работа, экзамен.

Литература

1. Вирт Н. Алгоритмы и структуры данных. Новая версия для Оберона + CD. – М.: ДМК Пресс, 2014. – 272с.

2. Зубов В.С., Шевченко И.В. Структуры и методы обработки данных. – М.: Информационно-издат. дом «Филинъ», 2004. – 304 с.

3. Ахо, А. В., Хопкрофт Джон, Ульман Джеффри Д. Структуры данных и алгоритмы.: Уч.пос.– М.: Издательский дом «Вильямс», 2000. – 384 с.

4. Гудрич М.Т., Тамасия Р. Структуры данных и алгоритмы в Java. - Мн.: Новое знание, 2003. – 671 с.

ЛЕКЦИЯ 1

Тема 1.1. Критерии оценки алгоритмов

Асимптотические характеристики

Алгоритм – это точное предписание о выполнении в определенном порядке некоторых операций, приводящих к решению всех задач данного класса.

Свойства алгоритма:

1) определенность (точность предписаний и однозначность результата);

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

3) дискретность (деление процесса решения на этапы, понятные человеку и ЭВМ);

4) результативность (результат должен быть обязательно – даже если его нет, должно быть сообщение об этом).

Способы описания алгоритмов (известны из курса «Программирование»):

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

2) математический (в виде формул, например формула для нахождения корней квадратного уравнения);

3) графический (схемы алгоритмов);

4) на языке программирования.

Важнейшей характеристикой алгоритма и соответствующей ему программы является их сложность, которая может оцениваться:

a) временем решения задачи (трудоемкостью алгоритма);

b) требуемой емкостью памяти.

Наиболее часто сложность алгоритма оценивают по порядку величины (порядка n, n² и т.д.). Этот метод применим как к временной, так и к емкостной сложности.

1. Временная оценка (оценка порядка)

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

1. Простое присваивание: а <-- b, будем считать ее сложность, равной 1;

2. Одномерная индексация a[i] : (адрес (a)+i*длина элемента), будем считать ее сложность, равной 2;

3. Арифметические операции: (*, /, -, +), будем считать их сложность, равной 1;

4. Операции сравнения: a < b, будем считать их сложность, равной 1;

5. Логические операции (l1) {or - |, and - &&, not - !} (l2), будем считать их сложность, равной 1;

С их помощью трудоемкость основных алгоритмических конструкций можно представить так.

1. Линейная конструкция из k последовательных блоков

Трудоемкость конструкции есть сумма трудоемкостей блоков, следующих друг за другом.

Θ =f₁+f₂+…+f_k,

где f_k – трудоемкость k-го блока.

2. Конструкция «Ветвление»

If (Условие) // then

Операторы

else

Операторы.

Общая трудоемкость конструкции «Ветвление» требует анализа вероятности выполнения операторов, стоящих после «Then» (р) и «Else» (1-р) и определяется как:

Θ = f_thenp + f_else(1-p),

где f_then и f_else – трудоемкости соответствующих ветвей.

3. Конструкция «Цикл»

for (i=1; i<= n;i++){

Тело цикла}

После сведения этой конструкции к элементарным операциям ее трудоемкость определяется как:

Θ =1+3*n+n* f_цикла,

где f_цикла – сложность тела цикла,

n – число его повторений,

3* n – трудоемкость изменения параметра и проверки условия выполнения цикла.

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

Рассмотрим примеры анализа простых алгоритмов.

Пример 1. Задача суммирования элементов квадратной матрицы размерностью n* n.

SumM (A, n; Sum)
Sum <-- 0
For i <-- 1 to n
For j <-- 1 to n
Sum <-- Sum + A[i,j]
end for
Return (Sum)
End

Алгоритм выполняет одинаковое количество операций при фиксированном значении n и, следовательно, является количественно-зависимым. Применение методики анализа конструкции «Цикл » дает:

Θ (n)=1+ f_{цикла по}_i = 1 + 1+ 3*n + n * f_{цикла по}_j =

1 + 1+ 3*n + n *(1+ 3*n + n *(2 + 2 + 1 + 1))

= 2 + 3n + n *(1 + 3n + 6 n) = 9n²+4 n +2. (1.1)

1.1. Общий случай определения временной сложности

Оценку сложности алгоритмов выполняют с использованием аппарата математического асимптотического анализа и выведения асимптотической оценки сложности.

Выражение (1.1) представляет собой точную оценку сложности алгоритмов. В теории алгоритмов они являются семейством функций, дающих множество значений, в том числе верхнее и нижнее. Основным свойством Θ(n) является то, что при увеличении размерности входных данных n время выполнения алгоритма возрастает с той же скоростью, что и функция f(n). Ее еще называют асимптотической.

Асимптотическая оценка сложности обозначается греческой буквой Θ (тета).

f(n) = Θ(g(n)), если существуют c₁, c₂>0 и n₀ такие, что c₁*g(n)<=f(n)<=c₂*g(n) , при n>n₀.

Функция g(n) является асимптотически точной оценкой сложности алгоритма - функции f(n). Приведенное неравенство называется асимптотическим, а само обозначение Θ символизирует множество функций, которые растут «так же быстро», как и функция g(n) – т.е. с точностью до некоторой константы c₁ или c₂.

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

Верхняя оценка сложности обозначается греческой буквой Ο (омикрон), и является множеством функций, которые растут не быстрее, чем g(n).

f(n)= Ο(g(n)), если существует c>0 и n₀ такие, что 0<=f(n)<=cg(n), при n>n₀.

Нижняя оценка сложности обозначается греческой буквой Ω (омега), и является множеством функций, которые растут не медленнее, чем g(n).

f(n)= Ω(g(n)), если существует c>0 и n0 такие, что 0<=cg(n)<=f(n), при n>n₀.

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

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

Обычно определение сложности алгоритма сводится к анализу

a) Циклов;

b) Вызовов методов и

c) Вызовов рекурсий.

Так, в примере 1 (нахождение суммы элементов квадратной матрицы) она определяется величиной O(n²), а в примере 2 (нахождение максимума в одномерном массиве) для всех случаев – O(n). Вообще для циклов вида:

for (i=1; i<= n;i++)

for (j=1; j<= n;j++)

for (k=1; k<= n;k++)

{Тело цикла}

сложность равна O(n³), т.е. пропорциональна числу повторений самого внутреннего цикла.