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

Структура лекции Введение в теорию Введение в теорию Ресурсы расходуемые алгоритмом Ресурсы расходуемые алгоритмом Абстрактная модель вычислений Абстрактная модель вычислений Зависимость от входных данных Зависимость от входных данных Асимптотический анализ алгоритмов Асимптотический анализ алгоритмов Основные классы алгоритмов Основные классы алгоритмов Область действия Область действия

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

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

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

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

1. Алгоритм рассматривается как набор операций и управляющих структур Базовые виды управляющих структур Базовые виды управляющих структур Составной оператор (begin end) Составной оператор (begin end) Условие (if then else, case) Условие (if then else, case) Цикл (for, while, repeat) Цикл (for, while, repeat) Основные виды операций Основные виды операций Логические (not, and, or, xor…) Логические (not, and, or, xor…) Арифметические (+, -, *, /, div, mod) Арифметические (+, -, *, /, div, mod) Математические функции (sin, cos, log, exp, power..) Математические функции (sin, cos, log, exp, power..) Вызов процедур и функций Вызов процедур и функций и др. и др.

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

3. Время работы алгоритма в целом равно сумме стоимостей составляющих его операций с учетом вложенности управляющих структур Управляющая структура Запись на языке Pascal Вычислительная сложность структуры 1 Составной оператор begin S 1 ; S 2 ; … end; 2Цикл for i := 1 to N do S; While U do S; Repeat S; Until U;, где N – число итераций цикла 3Условие if U then S 1 else S 2 ;

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

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

Зависимость от входных данных Временная сложность поиска числа в массиве зависит от содержимого массива А, от искомого числа х и количества элементов в массиве n : Для упрощения принимается правило: временную сложность алгоритма выражать, как функцию только размера входных данных, НЕзависящую от содержимого входных данных. Размер входных данных (N) – величина, характеризующая количество входной информации. ( зависит от задачи ) Упростить функцию до T Search (n) можно несколькими способами: 1. Наилучший случай – искомое число в первой ячейке T Search (n)=3 2. Наихудший случай – искомое число в последней ячейке T Search (n)=n+2 3. Средний случай – при равномерной распределении T Search (n)=(3+(n+2))/2

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

Асимптотический анализ Основные классы функции Вид функции Название класса функций Примеры и комментарии 1 «Постоянное время» Сумма двух первых чисел массива, доступ к i-му элементу массива. log 2 n = log n «Логарифмическое время» Бинарный поиск элемента в отсортированном массиве. n «Линейное время» Простой поиск числа в массиве, доступ к i-му элементу списка nlog 2 n «Время пропорциональное n log n» Сортировка массива слиянием или быстрая сортировка в среднем случае. n2n2 «Квадратичное время» Алгоритмы, перебирающие все пары элементов исходных данных, сортировка «пузырьком» в наихудшем случае. n3n3 «Кубическое время» Алгоритмы рассматривающие все тройки элементов исходных данных. … … … 2n2n2n2n «Экспоненциальное время» Алгоритмы, перебирающие все подмножества набора входных данных. n! «Факториальное время» Алгоритмы, перебирающие все комбинации элементов набора входных данных. «Полиномиальное время»

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

Асимптотический анализ Область действия ! Асимптотический анализ справедлив только для больших n. ! Асимптотический анализ справедлив только для больших n. Для малых n бывают случаи, когда алгоритм, относящийся к более эффективному классу, работает медленнее, чем алгоритм менее эффективного класса. Пример, метод сортировки «пузырьком» при малых n работает быстрее чем «быстрая» сортировка.

Чего ж сегодня изучали? Введение в теорию Введение в теорию Ресурсы расходуемые алгоритмом Ресурсы расходуемые алгоритмом Абстрактная модель вычислений Абстрактная модель вычислений Зависимость от входных данных Зависимость от входных данных Асимптотический анализ алгоритмов Асимптотический анализ алгоритмов Основные классы алгоритмов Основные классы алгоритмов Область действия Область действия

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

Спасибо за внимание!! надеюсь не уснули…