Содержание
- 2. План Лекция 16 План Эффективность алгоритмов Эффективность алгоритмов и ее измерение Временная сложность алгоритма в зависимости
- 3. Эффективность алгоритмов Эффективность алгоритмов и ее измерение Временная сложность алгоритма в зависимости от размера задачи Худший,
- 4. Эффективность алгоритмов Эффективность алгоритмов Часто для решения одной и той же задачи могут быть использованы различные
- 5. Эффективность алгоритмов Эффективность алгоритмов Основные ресурсы Время выполнения алгоритма Определяется количеством тривиальных шагов, необходимых для решения
- 6. Эффективность алгоритмов Как измерять эффективность алгоритмов? Возможные пути Экспериментальное (эмпирическое) сравнение алгоритмов Сравнение затрат времени (памяти)
- 7. Эффективность алгоритмов От чего зависит время выполнения? От загрузки машины От операционной системы От компилятора От
- 8. Эффективность алгоритмов Зависимость времени от размера Пример 1. Поиск максимума int largest(int array[], int n) {
- 9. Эффективность алгоритмов Характер роста функций В зависимости от вида функции T(n) характер ее роста может быть
- 10. Эффективность алгоритмов Наилучший, наихудший и средний случаи При том же размере входных данных n время выполнения
- 11. Эффективность алгоритмов Какой из случаев оценивать? Анализировать поведение алгоритма в среднем – наиболее разумно, но наиболее
- 12. Эффективность алгоритмов Ускорять компьютер или алгоритм? Что произойдет, если использовать компьютер в 10 раз производительнее?
- 13. Эффективность алгоритмов Ускорять компьютер или алгоритм? Абсолютные временные затраты алгоритмов разной сложности
- 14. Асимптотический анализ алгоритмов Цели асимптотического анализа О-символика Примеры асимптотического анализа алгоритмов Асимптотическая сложность задач Временная и
- 15. Асимптотический анализ алгоритмов Асимптотический анализ Экспериментальное сравнение алгоритмов трудоемко На практике чаще используется более простой асимптотический
- 16. Асимптотический анализ алгоритмов Асимптотический анализ В асимптотическом анализе алгоритмов используются обозначения, принятые в математическом асимптотическом анализе
- 17. Асимптотический анализ алгоритмов Асимптотический анализ: O() Определение Говорят, что неотрицательная функция f(n) есть O(g(n)), если существуют
- 18. Асимптотический анализ алгоритмов Асимптотический анализ: O() Другими словами Запись f(n)=O(g(n)) означает, что f(n) принадлежит классу функций,
- 19. Асимптотический анализ алгоритмов Асимптотический анализ: O() O() указывает верхнюю границу При выборе верхней границы наиболее интересна
- 20. Асимптотический анализ алгоритмов Асимптотический анализ: O() Пример 1. Линейный поиск в массиве (средний случай) T(n) =
- 21. Асимптотический анализ алгоритмов Асимптотический анализ: O() Пример 2. Пусть T(n) = c1n2 + c2n в среднем
- 22. Асимптотический анализ алгоритмов Асимптотический анализ: O() Распространенная ошибка “Лучшим для моего алгоритма является случай n=1, т.к.
- 23. Асимптотический анализ алгоритмов Асимптотический анализ: O() Распространенная ошибка Часто худший случай путают с верхней границей Верхняя
- 24. Асимптотический анализ алгоритмов Асимптотический анализ: Ω() Определение Говорят, что неотрицательная функция f(n) есть Ω(g(n)), если существуют
- 25. Асимптотический анализ алгоритмов Асимптотический анализ: Ω() Пример. T(n) = c1n2 + c2n. c1n2 + c2n ≥
- 26. Асимптотический анализ алгоритмов Асимптотический анализ: Θ() Определение Говорят, что неотрицательная функция f(n) есть Θ(g(n)), если существуют
- 27. Асимптотический анализ алгоритмов Асимптотический анализ Правила упрощения Транзитивность Если f(n) есть O(g(n)) и g(n) есть O(h(n)),
- 28. Асимптотический анализ алгоритмов Асимптотический анализ Пример 1 Присвоение требует константного времени, поэтому имеет сложность Θ(1) a
- 29. Асимптотический анализ алгоритмов Асимптотический анализ Пример 3 Первая строка есть Θ(1) Вложенный цикл есть Σi =
- 30. Асимптотический анализ алгоритмов Асимптотический анализ Пример 4 Первая пара вложенных циклов – n2 шагов Вторая пара
- 31. Асимптотический анализ алгоритмов Асимптотический анализ Пример 5 Первая пара циклов: Σn для k=1…log n есть Θ(n
- 32. Бинарный поиск Идея алгоритма Временная сложность алгоритма
- 33. Организация курса Бинарный поиск Возможно ли ускорить линейный алгоритм поиска элемента в массиве? (Θ(n)) Да, если
- 34. Организация курса Бинарный поиск На каждом шаге центральный элемент A[m] проверяется на совпадение с искомым K
- 35. Асимптотический анализ алгоритмов Бинарный поиск Код // Возвращает позицию элемента K // в упорядоченном массиве размера
- 36. Асимптотический анализ алгоритмов Асимптотический анализ различных управляющих конструкций Цикл while анализируется так же как и for
- 37. Асимптотический анализ алгоритмов Асимптотический анализ сложности задач Анализ задачи = анализ классов алгоритмов Верхняя граница: верхняя
- 38. Асимптотический анализ алгоритмов Асимптотический анализ сложности задач Пример Нет смысла говорить о верхних/нижних границах, если известно
- 39. Асимптотический анализ алгоритмов Асимптотический анализ: несколько параметров Упорядочить по популярности C значений пикселов на изображении, содержащем
- 40. Асимптотический анализ алгоритмов Асимптотический анализ: затраты памяти Асимптотический анализ затрат памяти проводится совершенно аналогично анализу временных
- 41. Асимптотический анализ алгоритмов Баланс «затраты памяти»/«затраты времени» Временные затраты алгоритма могут быть понижены, если повысить расход
- 43. Скачать презентацию