🗊Презентация Разработка и анализ алгоритмов

Разработка и анализ алгоритмов

Литература по теме Кормен Т., Лейзерсон Ч., Ривест Р. «Алгоритмы. Построение и анализ» (главы 1, 2, 4) Левитин А. «Алгоритмы. Введение в разработку и анализ» (глава 2) Ахо А., Хопкрофт Дж., Ульман Дж. «Построение и анализ вычислительных алгоритмов» (глава 1) Майкл Ласло «Вычислительная геометрия и компьютерная графика на C++» (глава 2)

Анализ вычислительной сложности алгоритмов

Алгоритм Евклида (III в. до н.э)

Псевдокод

Псевдокод

Введение

Ресурсы, расходуемые алгоритмом (вычислительные ресурсы) Вычислительные ресурсы – возможности, обеспечиваемые компонентами вычислительной системы, расходуемые (занимаемые) в процессе её работы. Виды вычислительных ресурсов: Машинное (однопроцессорное) время (Т) – время работы алгоритма для решения задачи. Оперативная память (М) – объем памяти с произвольным доступом, необходимый алгоритму для решения поставленной задачи. Долговременная память – место на жёстком диске. Пропускная способность сети (трафик). Энергия поглощаемая и выделяемая. другие… Часто удается сокращать объем потребления одного вида ресурса за счет увеличения потребления другого.

Абстрактная модель вычислений Основные положения Алгоритм рассматривается как набор операций и управляющих структур. Каждому виду операций сопоставляется временная стоимость в абстрактных единицах времени (шагах). Время работы алгоритма в целом равно сумме стоимостей составляющих его операций с учетом вложенности управляющих структур.

1. Алгоритм рассматривается как набор операций и управляющих структур

2. Каждой операции сопоставляется временная стоимость в абстрактных единицах времени (шагах) Упрощенная модель вычислений - временная стоимость всех операций считается одинаковой и равной 1 шагу.

3. Время работы алгоритма в целом равно сумме стоимостей составляющих его операций с учетом вложенности управляющих структур

Оценка сложности

Оценка сложности

Сортировка вставками

Сортировка вставками

Сортировка вставками

Худший случай

Пример анализа вычислительной сложности алгоритма //Алгоритм простого последовательного поиска целого числа x в массиве A function Search(A: array[1..n] of integer; x: integer): integer; var i: integer; begin //В цикле обход элементов массива for i := 1 to n do //Если текущий элемент равен искомому if A[i] = x then begin //то вернуть индекс элемента result := i; //и выйти из процедуры exit; end; //вернуть признак того, что элемент не найден result := -1; end;

Пример анализа вычислительной сложности алгоритма (в упрощенной модели вычислений) //Алгоритм простого последовательного поиска целого числа x в массиве A function Search(A: array[1..n] of integer; x: integer): integer; var i: integer; begin //УС1 //В цикле обход элементов массива for i := 1 to n do //УС2 //Если текущий элемент равен искомому if A[i] = x then //УС3 begin //УС4 //то вернуть индекс элемента result := i; //и выйти из процедуры exit; end; //вернуть признак того, что элемент не найден result := -1; end;

Зависимость от входных данных

Асимптотический анализ вычислительной сложности алгоритмов Асимптотический анализ – анализ поведения функции временной сложности алгоритма Т(n) при n c целью выбора ближайшей более простой (как правило, элементарной) функции.

Асимптотический анализ Основные классы функции

Асимптотический анализ Графики основных классов функций

Асимптотический анализ Область действия ! Асимптотический анализ справедлив только для больших n.

Асимптотический анализ

Аналогии

Примеры

Основные формулы суммирования

Пример

Метод итераций

Сортировка слиянием

Анализ

Основная теорема