Математические модели. Классификация порядков роста. Теория алгоритмов. Сортировка выбором презентация
Содержание
- 2. Математические модели для времени выполнения Общее время выполнения. Сумма: стоимость каждой
- 3. Стоимость основных операций
- 4. Стоимость основных операций Ошибка новичков: неправильная оценка конкатенации строк
- 5. Пример: 1-Sum Подсчет количества инструкций, как функции от N.
- 6. Пример: 2-Sum Подсчет количества инструкций, как функции от N.
- 7. Упрощение вычислений
- 8. Упрощение 1: модель стоимости Модель стоимости. Использовать некоторые основные операции для
- 9. Упрощение 2: тильда-нотация Оценить время выполнение (или память), как функцию от
- 10. Упрощение 2: тильда-нотация Оценить время выполнение (или память), как функцию от
- 11. Пример: 2-Sum Нижняя оценка. Использовать модель стоимости и тильда-нотацию для упрощение
- 12. Пример: 3-Sum Нижняя оценка. Использовать модель стоимости и тильда-нотацию для упрощение
- 13. Оценка дискретной суммы Как оценить дискретную сумму? Средствами дискретной математики. Заменить
- 14. Математическая модель для времени выполнения В принципе, всегда возможно построить точную
- 15. Классификация порядков роста
- 16. Общая классификация порядков роста Малое число функций описывающих порядок роста основных
- 17. Общая классификация порядков роста
- 18. Практическое применение порядков роста Нижняя оценка. Нужны линейные или линейно-логарифмические алгоритмы,
- 19. Бинарный поиск Цель. Найти индекс ключа в отсортированном массиве Бинарный поиск
- 20. Бинарный поиск: реализация Впервые бинарный поиск был опубликован в 1946; первая
- 21. Бинарный поиск: математический анализ Предположение. Бинарный поиск использует 1 + lg
- 22. N2log N алгоритм для 3-Sum Алгоритм основанный на сортировке Шаг 1:
- 23. Сравнение программ Гипотеза. Основанный на сортировке 3-Sum алгоритм N2log N однозначно
- 24. Теория алгоритмов
- 25. Типы анализа Лучший случай. Нижняя граница по стоимости Определяется самыми «простыми»
- 26. Типы анализа Лучший случай. Нижняя граница по стоимости Худший случай. Верхняя
- 28. Пример: два алгоритма сортировки Быстрая сортировка Количество сравнений в худшем случае:
- 30. Сортировка выбором
- 31. Сортировка выбором На итерации i найти минимальный оставшийся элемент с индексом
- 32. Сортировка выбором Алгоритм. Сканирование идет слева направо Элементы слева от стрелки
- 33. Сортировка выбором: внутренний цикл
- 34. Сортировка выбором: реализация на Java
- 35. Сортировка выбором: математический анализ Утверждение. Сортировка выбором использует (N-1) + (N-2)
- 36. Скачать презентацию
Слайды и текст этой презентации
Скачать презентацию на тему Математические модели. Классификация порядков роста. Теория алгоритмов. Сортировка выбором можно ниже: