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