Анализ алгоритмов. (Лекция 16) - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Анализ алгоритмов. (Лекция 16), слайд №1

Анализ алгоритмов. (Лекция 16), слайд №2

Анализ алгоритмов. (Лекция 16), слайд №3

Анализ алгоритмов. (Лекция 16), слайд №4

Анализ алгоритмов. (Лекция 16), слайд №5

Анализ алгоритмов. (Лекция 16), слайд №6

Анализ алгоритмов. (Лекция 16), слайд №7

Анализ алгоритмов. (Лекция 16), слайд №8

Анализ алгоритмов. (Лекция 16), слайд №9

Анализ алгоритмов. (Лекция 16), слайд №10

Анализ алгоритмов. (Лекция 16), слайд №11

Анализ алгоритмов. (Лекция 16), слайд №12

Анализ алгоритмов. (Лекция 16), слайд №13

Анализ алгоритмов. (Лекция 16), слайд №14

Анализ алгоритмов. (Лекция 16), слайд №15

Анализ алгоритмов. (Лекция 16), слайд №16

Анализ алгоритмов. (Лекция 16), слайд №17

Анализ алгоритмов. (Лекция 16), слайд №18

Анализ алгоритмов. (Лекция 16), слайд №19

Анализ алгоритмов. (Лекция 16), слайд №20

Анализ алгоритмов. (Лекция 16), слайд №21

Анализ алгоритмов. (Лекция 16), слайд №22

Анализ алгоритмов. (Лекция 16), слайд №23

Анализ алгоритмов. (Лекция 16), слайд №24

Анализ алгоритмов. (Лекция 16), слайд №25

Анализ алгоритмов. (Лекция 16), слайд №26

Анализ алгоритмов. (Лекция 16), слайд №27

Анализ алгоритмов. (Лекция 16), слайд №28

Анализ алгоритмов. (Лекция 16), слайд №29

Анализ алгоритмов. (Лекция 16), слайд №30

Анализ алгоритмов. (Лекция 16), слайд №31

Анализ алгоритмов. (Лекция 16), слайд №32

Анализ алгоритмов. (Лекция 16), слайд №33

Анализ алгоритмов. (Лекция 16), слайд №34

Анализ алгоритмов. (Лекция 16), слайд №35

Анализ алгоритмов. (Лекция 16), слайд №36

Анализ алгоритмов. (Лекция 16), слайд №37

Анализ алгоритмов. (Лекция 16), слайд №38

Анализ алгоритмов. (Лекция 16), слайд №39

Анализ алгоритмов. (Лекция 16), слайд №40

Анализ алгоритмов. (Лекция 16), слайд №41

Анализ алгоритмов. (Лекция 16), слайд №42

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Анализ алгоритмов. (Лекция 16). Доклад-сообщение содержит 42 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Анализ алгоритмов Алтайский государственный университет Факультет математики и ИТ Кафедра информатики Барнаул 2014

Слайд 2

Описание слайда:

Лекция 16 План Эффективность алгоритмов Эффективность алгоритмов и ее измерение Временная сложность алгоритма в зависимости от размера задачи Худший, средний и лучший случаи Что ускорять: компьютер или алгоритм? Асимптотический анализ алгоритмов Цели асимптотического анализа О-символика Примеры асимптотического анализа алгоритмов Асимптотическая сложность задач Временная и пространственная сложность Бинарный поиск Идея алгоритма Временная сложность алгоритма

Слайд 3

Описание слайда:

Эффективность алгоритмов Эффективность алгоритмов и ее измерение Временная сложность алгоритма в зависимости от размера задачи Худший, средний и лучший случаи Что ускорять: компьютер или алгоритм?

Слайд 4

Описание слайда:

Эффективность алгоритмов Часто для решения одной и той же задачи могут быть использованы различные алгоритмы Как выбрать алгоритм? При разработке программ преследуется две (часто конфликтующие) цели Разработать алгоритм, простой для понимания, кодирования и отладки Предмет изучения дисциплины «Software Engineering» Разработать алгоритм, эффективно использующий ресурсы компьютера Предмет изучения дисциплины «Структуры данных и анализ алгоритмов»

Слайд 5

Описание слайда:

Эффективность алгоритмов Основные ресурсы Время выполнения алгоритма Определяется количеством тривиальных шагов, необходимых для решения задачи Пространство, используемое алгоритмом Определяется объёмом оперативной памяти или памяти на носителе данных Остается «за скобками» : Трудоемкость кодирования алгоритма Определяется временными затратами программиста на кодирование и отладку алгоритма

Слайд 6

Описание слайда:

Как измерять эффективность алгоритмов? Возможные пути Экспериментальное (эмпирическое) сравнение алгоритмов Сравнение затрат времени (памяти) при непосредственном запуске программ Асимптотический анализ алгоритмов Построение теоретических оценок затрат времени (памяти) в зависимости от различных факторов

Слайд 7

Описание слайда:

От чего зависит время выполнения? От загрузки машины От операционной системы От компилятора От специфики значений входных данных От размера задачи Зависимость времени выполнения T от размера задачи n выражается некоторой функцией T(n)

Слайд 8

Описание слайда:

Зависимость времени от размера Пример 1. Поиск максимума

Слайд 9

Описание слайда:

Характер роста функций В зависимости от вида функции T(n) характер ее роста может быть разным

Слайд 10

Описание слайда:

Наилучший, наихудший и средний случаи При том же размере входных данных n время выполнения алгоритма может быть разным Пример. Последовательный поиск элемента K в массиве размера n Элементы массива, начиная с первого, поочередно просматриваются до тех пор пока не найден K Наилучший случай: K найден на 1-й позиции Наихудший случай: K найден на n-й позиции Средний случай: в среднем K обнаружится после (n+1)/2 сравнений

Слайд 11

Описание слайда:

Какой из случаев оценивать? Анализировать поведение алгоритма в среднем – наиболее разумно, но наиболее трудно Требуется знание распределения значений (частоты возникновения тех или иных данных) Поведение алгоритма в худшем случае важно анализировать в алгоритмах реального времени Пример – системы диспетчеризации транспорта

Слайд 12

Описание слайда:

Ускорять компьютер или алгоритм? Что произойдет, если использовать компьютер в 10 раз производительнее?

Слайд 13

Описание слайда:

Ускорять компьютер или алгоритм? Абсолютные временные затраты алгоритмов разной сложности

Слайд 14

Описание слайда:

Асимптотический анализ алгоритмов Цели асимптотического анализа О-символика Примеры асимптотического анализа алгоритмов Асимптотическая сложность задач Временная и пространственная сложность

Слайд 15

Описание слайда:

Асимптотический анализ Экспериментальное сравнение алгоритмов трудоемко На практике чаще используется более простой асимптотический анализ алгоритмов Асимптотический анализ алгоритмов направлен на получение и сравнение теоретических оценок сложности алгоритмов (вида T(n)) при достаточно больших n

Слайд 16

Описание слайда:

Асимптотический анализ В асимптотическом анализе алгоритмов используются обозначения, принятые в математическом асимптотическом анализе O-символика o(f(n)) оценка порядка малости O(f(n)) оценка верхней границы (f(n)) оценка нижней границы (f(n)) оценка верхней и нижней границы

Слайд 17

Описание слайда:

Асимптотический анализ: O() Определение Говорят, что неотрицательная функция f(n) есть O(g(n)), если существуют константы c>0 и n0>0, такие что f(n) ≤ cg(n) для любых n > n0. Пример использования Временная сложность алгоритма есть O(n2) в [лучшем, среднем, худшем] случае. Смысл Для всех достаточно больших входных данных (n>n0), алгоритм всегда выполняется менее, чем за cg(n) шагов в [лучшем, среднем, худшем] случае

Слайд 18

Описание слайда:

Асимптотический анализ: O() Другими словами Запись f(n)=O(g(n)) означает, что f(n) принадлежит классу функций, которые растут не быстрее, чем функция g(n) с точностью до постоянного множителя. Пример. Если T(n) = 3n2, то T(n) есть O(n2)

Слайд 19

Описание слайда:

Асимптотический анализ: O() O() указывает верхнюю границу При выборе верхней границы наиболее интересна наименьшая из возможных Пример. Хотя T(n) = 3n2 есть O(n3), мы выбираем O(n2) как более информативный вариант

Слайд 20

Описание слайда:

Асимптотический анализ: O() Пример 1. Линейный поиск в массиве (средний случай) T(n) = csn/2 Для всех n > 1, csn/2 ≤ csn Таким образом, по определению, T(n) есть O(n) при n0 = 1 и c = cs

Слайд 21

Описание слайда:

Асимптотический анализ: O() Пример 2. Пусть T(n) = c1n2 + c2n в среднем случае c1n2 + c2n ≤ c1n2 + c2n2 ≤ (c1 + c2)n2 для всех n > 1 T(n) ≤ cn2 при c = c1 + c2 и n0 = 1. Тогда T(n) есть O(n2) по определению Пример 3. T(n) = c. Говорят: T(n) есть O(1).

Слайд 22

Описание слайда:

Асимптотический анализ: O() Распространенная ошибка “Лучшим для моего алгоритма является случай n=1, т.к. при этом алгоритм наиболее быстр” – НЕКОРРЕКТНО! O() описывает характер роста по мере стремления n к  Лучшим случаем называют такой, при котором на обработку входных данных размера n тратится наименьшее время по сравнению с прочими данными того же размера

Слайд 23

Описание слайда:

Асимптотический анализ: O() Распространенная ошибка Часто худший случай путают с верхней границей Верхняя граница описывает характер роста по мере стремления n к  Худшим случаем называют такой, при котором на обработку входных данных размера n тратится наибольшее время по сравнению с прочими данными того же размера

Слайд 24

Описание слайда:

Асимптотический анализ: () Определение Говорят, что неотрицательная функция f(n) есть (g(n)), если существуют константы c>0 и n0>0, такие что f(n) ≥ cg(n) для любых n > n0. Смысл Для всех достаточно больших входных данных (n>n0), алгоритм всегда выполняется более, чем за cg(n) шагов Нижняя граница Оценка (g(n)) задает нижнюю асимптотическую оценку роста функции f(n) и определяет класс функций, которые растут не медленнее, чем g(n) с точностью до постоянного множителя

Слайд 25

Описание слайда:

Асимптотический анализ: () Пример. T(n) = c1n2 + c2n. c1n2 + c2n ≥ c1n2 для любых n > 1 T(n) ≥ cn2 для c = c1 и n0 = 1 Таким образом, T(n) есть (n2) по определению Из всех нижних границ интересна наибольшая

Слайд 26

Описание слайда:

Асимптотический анализ: () Определение Говорят, что неотрицательная функция f(n) есть (g(n)), если существуют константы c1>0, c2>0 и n0>0, такие что c1g(n) ≤ f(n) ≤ c2g(n) для любых n > n0. Функция f(n) есть (g(n)), если она одновременно есть (g(n)) и O(g(n)) Смысл Асимптотическое равенство (с точностью до константы) Полностью описывает характер роста функции

Слайд 27

Описание слайда:

Асимптотический анализ Правила упрощения Транзитивность Если f(n) есть O(g(n)) и g(n) есть O(h(n)), то f(n) есть O(h(n)) Игнорирование констант Если f(n) есть O(kg(n)) для любой константы k > 0, то f(n) есть O(g(n)) Отбрасывание членов низких порядков Если f1(n) есть O(g1(n)) и f2(n) есть O(g2(n)), то (f1 + f2)(n) есть O(max(g1(n), g2(n))) Мултипликативность Если f1(n) есть O(g1(n)) и f2(n) есть O(g2(n)), то f1(n)f2(n) есть O(g1(n)g2(n))

Слайд 28

Описание слайда:

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

Слайд 29

Описание слайда:

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

Слайд 30

Описание слайда:

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

Слайд 31

Описание слайда:

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

Слайд 32

Описание слайда:

Бинарный поиск Идея алгоритма Временная сложность алгоритма

Слайд 33

Описание слайда:

Бинарный поиск Возможно ли ускорить линейный алгоритм поиска элемента в массиве? ((n)) Да, если массив упорядочен Наличие порядка позволяет использовать принцип «разделяй и властвуй»: на каждом шаге уменьшая вдвое размер решаемой задачи Бинарный поиск – реализация стратегии «разделяй и властвуй» в чистом виде

Слайд 34

Описание слайда:

Бинарный поиск На каждом шаге центральный элемент A[m] проверяется на совпадение с искомым K Если A[m] = K, конец алгоритма Если A[m] < K, то далее решается задача поиска в подмассиве A[m]…A[n]? иначе – в подмассиве A[1]…A[m]

Слайд 35

Описание слайда:

Бинарный поиск Код

Слайд 36

Описание слайда:

Асимптотический анализ различных управляющих конструкций Цикл while анализируется так же как и for Условный оператор if оценивается по наиболее сложной ветви then/else Вероятность срабатывания ветвей не должна зависеть от n Оператор ветвления switch оценивается по наиболее сложной ветви case Вероятность срабатывания ветвей не должна зависеть от n Сложность вызова подпрограммы равна сложности подпрограммы

Слайд 37

Описание слайда:

Асимптотический анализ сложности задач Анализ задачи = анализ классов алгоритмов Верхняя граница: верхняя граница сложности наилучшего из известных алгоритмов решения задачи Нижняя граница: нижняя граница для всех известных алгоритмов решения задачи

Слайд 38

Описание слайда:

Асимптотический анализ сложности задач Пример Нет смысла говорить о верхних/нижних границах, если известно точное количество операций Пример неточных знаний о задаче: сортировка 1. Сложность ввода/вывода: (n). 2. Пузырьковая сортировка или вставками: O(n2). 3. Более эффективные методы (Quicksort, Mergesort, Heapsort, и т.д.): O(n log n). 4. Для некоторых типов данных существуют методы со сложностью O(n).

Слайд 39

Описание слайда:

Асимптотический анализ: несколько параметров Упорядочить по популярности C значений пикселов на изображении, содержащем P пикселов Если в качестве размера данных использовать P, то время работы есть (P log P) Более точно: (P + C log C)

Слайд 40

Описание слайда:

Асимптотический анализ: затраты памяти Асимптотический анализ затрат памяти проводится совершенно аналогично анализу временных затрат Обычно такая потребность возникает при построении структур данных

Слайд 41

Описание слайда:

Баланс «затраты памяти»/«затраты времени» Временные затраты алгоритма могут быть понижены, если повысить расход памяти и наоборот: Жертвуя временем, можно сэкономить память Принцип баланса «время»/«дисковое пространство»: Чем меньше затраты дискового пространства, тем быстрее программа

Слайд 42

Описание слайда:

Вопросы? Эффективность алгоритмов Эффективность алгоритмов и ее измерение Временная сложность алгоритма в зависимости от размера задачи Худший, средний и лучший случаи Что ускорять: компьютер или алгоритм? Асимптотический анализ алгоритмов Цели асимптотического анализа О-символика Примеры асимптотического анализа алгоритмов Асимптотическая сложность задач Временная и пространственная сложность Бинарный поиск Идея алгоритма Временная сложность алгоритма