Разделы презентаций
- Разное
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Асимптотика
Содержание
- 1. Асимптотика
- 2. ВведениеАсимптотика – это поведение функции в особых
- 3. ЗадачаСколько операций требуется для выполнения данного фрагмента кода?
- 4. Количество элементарных операций, которое алгоритм выполняет за
- 5. ПримерыO(N2)O(1) O(N) O(log(N))
- 6. ЗадачаОцените асимптотику данного фрагмента кода.
- 7. Как это помогает решать задачи?Пусть асимптотика вашего
- 8. Основные классы сложности функций
- 9. Скачать презентанцию
ВведениеАсимптотика – это поведение функции в особых точках, чаще всего при стремлении аргумента или функции к бесконечности. Асимптотику используют для оценки времени выполнения алгоритма.
Слайды и текст этой презентации
Слайд 2Введение
Асимптотика – это поведение функции в особых точках, чаще всего
при стремлении аргумента или функции к бесконечности.
оценки времени выполнения алгоритма.
Слайд 4Количество элементарных операций, которое алгоритм выполняет за время своей работы
можно выразить математической функцией.
Параметрами данной функции служат переменные, влияющие на
количество операций, выполняемое алгоритмом.Асимптотическая оценка такой функции будет являться оценкой эффективности алгоритма.
Асимптотика обозначается O(f(N)).
Константы не влияют на асимптотическую оценку. То есть O(12) = O(1), O(5*N) = O(N) и так далее.
Элементарными считаются операции +,-,*,/,%,= и т.п.
Слайд 7Как это помогает решать задачи?
Пусть асимптотика вашего алгоритма O(N4).
Пусть по
условию задачи 1 ≤ N ≤ 100.
Тогда в худшем случае
на выполнения алгоритма потребуется 1004 = 108 операций.Современные процессоры работают на чистоте в несколько ГГц, то есть за 1 секунду они выполняют несколько миллиардов операций. Будем считать, что это 109 операций в секунду.
Таким образом ваш алгоритм будет выполняться 108 / 109 = 0.1с
