Презентация Математические модели. Классификация порядков роста. Теория алгоритмов. Сортировка выбором онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Математические модели. Классификация порядков роста. Теория алгоритмов. Сортировка выбором абсолютно бесплатно. Урок-презентация на эту тему содержит всего 35 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:35 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:2.56 MB
- Просмотров:136
- Скачиваний:2
- Автор:неизвестен
Слайды и текст к этой презентации:
№1 слайд
Содержание слайда: Математические модели
№2 слайд
Содержание слайда: Математические модели для времени выполнения
Общее время выполнения. Сумма: стоимость каждой операции * частоту, для всех операций
Анализ программ нужно производить на определенном наборе операций
Стоимость зависит от компьютера и компилятора
Частота зависит от алгоритма и входных данных
№3 слайд
Содержание слайда: Стоимость основных операций
№4 слайд
Содержание слайда: Стоимость основных операций
Ошибка новичков: неправильная оценка конкатенации строк
№5 слайд
Содержание слайда: Пример: 1-Sum
Подсчет количества инструкций, как функции от N.
№6 слайд
Содержание слайда: Пример: 2-Sum
Подсчет количества инструкций, как функции от N.
№7 слайд
Содержание слайда: Упрощение вычислений
№8 слайд
Содержание слайда: Упрощение 1: модель стоимости
Модель стоимости. Использовать некоторые основные операции для приближенного расчета времени выполнения.
№9 слайд
Содержание слайда: Упрощение 2: тильда-нотация
Оценить время выполнение (или память), как функцию от входных данных N
Игнорировать младшие члены
Когда N велико, младшие члены незначительны
Когда N мало, мы не о чем не заботимся
№10 слайд
Содержание слайда: Упрощение 2: тильда-нотация
Оценить время выполнение (или память), как функцию от входных данных N
Игнорировать младшие члены
Когда N велико, младшие члены незначительны
Когда N мало, мы не о чем не заботимся
№11 слайд
Содержание слайда: Пример: 2-Sum
Нижняя оценка. Использовать модель стоимости и тильда-нотацию для упрощение вычислений
№12 слайд
Содержание слайда: Пример: 3-Sum
Нижняя оценка. Использовать модель стоимости и тильда-нотацию для упрощение вычислений
№13 слайд
Содержание слайда: Оценка дискретной суммы
Как оценить дискретную сумму?
Средствами дискретной математики.
Заменить сумму на определенный интеграл и посчитать
№14 слайд
Содержание слайда: Математическая модель для времени выполнения
В принципе, всегда возможно построить точную математическую модель.
На практике
Формула может быть сложной
Могут понадобиться дополнительные математические знания
Точные модели лучше оставить экспертам
№15 слайд
Содержание слайда: Классификация порядков роста
№16 слайд
Содержание слайда: Общая классификация порядков роста
Малое число функций описывающих порядок роста основных алгоритмов
1, log N, N, Nlog N, N2, N3 и 2N
№17 слайд
Содержание слайда: Общая классификация порядков роста
№18 слайд
Содержание слайда: Практическое применение порядков роста
Нижняя оценка. Нужны линейные или линейно-логарифмические алгоритмы, чтобы идти в ногу с законом Мура.
№19 слайд
Содержание слайда: Бинарный поиск
Цель. Найти индекс ключа в отсортированном массиве
Бинарный поиск
Ключ меньше — идем влево
Ключ больше — идем вправо
Равен — возвращаем результат
№20 слайд
Содержание слайда: Бинарный поиск: реализация
Впервые бинарный поиск был опубликован в 1946; первая безошибочная реализация в 1962
Ошибка в Java.binarySearch() найдена в 2006
№21 слайд
Содержание слайда: Бинарный поиск: математический анализ
Предположение. Бинарный поиск использует 1 + lg N сравнений ключа в отсортированном массиве N
T(N) количество сравнений ключа в отсортированном массиве размером <= N
T(N) <= T(N / 2) + 1, для N > 1, с T(1) = 1
№22 слайд
Содержание слайда: N2log N алгоритм для 3-Sum
Алгоритм основанный на сортировке
Шаг 1: Сортировка N чисел
Шаг 2: Для каждой пары чисел a[i] и a[j] сделать бинарный поиск для -(a[i] + a[j])
Анализ. Порядок роста N2log N
Шаг 1: N2 сортировка вставками
Шаг 2: N2log N бинарный поиск
№23 слайд
Содержание слайда: Сравнение программ
Гипотеза. Основанный на сортировке 3-Sum алгоритм N2log N однозначно быстрее метода грубой силы N3
№24 слайд
Содержание слайда: Теория алгоритмов
№25 слайд
Содержание слайда: Типы анализа
Лучший случай. Нижняя граница по стоимости
Определяется самыми «простыми» входными данными
Цель для любых входных данных
Худший случай. Верхняя граница
Определяется «самыми сложными» входными данными
Предоставляет гарантии для всех возможных входных данных
Средний случай. Ожидаемая стоимость для случайных входных данных
Нужна модель для случайных входных данных
Предоставляет возможность предсказывать производительность.
№26 слайд
Содержание слайда: Типы анализа
Лучший случай. Нижняя граница по стоимости
Худший случай. Верхняя граница
Средний случай. Ожидаемая стоимость для случайных входных данных
Реальные входные данные могут не соответствовать модели
Нужно понимать, что может быть на входе, чтобы эффективно обрабатывать данные
Подход 1: строить модель для худшего случая
Подход 2: строить модель для случайных данных, в зависимости от вероятностных характеристик (если они даны)
№27 слайд
Содержание слайда:
№28 слайд
Содержание слайда: Пример: два алгоритма сортировки
Быстрая сортировка
Количество сравнений в худшем случае: N2
O(N2)
Сортировка слиянием
Количество сравнений в худшем случае: N logN
O(N logN)
Известно, что на практике быстрая сортировка в два раза быстрее и использует в два раза меньше памяти, чем сортировка слиянием.
Не используйте O для предсказания производительности и сравнения алгоритмов
№29 слайд
Содержание слайда:
№30 слайд
Содержание слайда: Сортировка выбором
№31 слайд
Содержание слайда: Сортировка выбором
На итерации i найти минимальный оставшийся элемент с индексом min
Поменять местами a[i] и a[min]
Видео 1
№32 слайд
Содержание слайда: Сортировка выбором
Алгоритм. Сканирование идет слева направо
Элементы слева от стрелки отсортированы и не меняются
Нет элемента справа от стрелки, который был бы меньше элемента слева от стрелки
№33 слайд
Содержание слайда: Сортировка выбором: внутренний цикл
№34 слайд
Содержание слайда: Сортировка выбором: реализация на Java
№35 слайд
Содержание слайда: Сортировка выбором: математический анализ
Утверждение. Сортировка выбором использует (N-1) + (N-2) + … + 1 + 0 ~ N2/2 сравнений и N перестановок
Скачать все slide презентации Математические модели. Классификация порядков роста. Теория алгоритмов. Сортировка выбором одним архивом:
