Рекурсия. Сортировка слиянием. Восходящая сортировка слиянием. Сложность сортировки. Устойчивость сортировок

Нажмите для полного просмотра!

Рекурсия. Сортировка слиянием. Восходящая сортировка слиянием. Сложность сортировки. Устойчивость сортировок, слайд №2

Рекурсия. Сортировка слиянием. Восходящая сортировка слиянием. Сложность сортировки. Устойчивость сортировок, слайд №3

Рекурсия. Сортировка слиянием. Восходящая сортировка слиянием. Сложность сортировки. Устойчивость сортировок, слайд №4

Рекурсия. Сортировка слиянием. Восходящая сортировка слиянием. Сложность сортировки. Устойчивость сортировок, слайд №5

Рекурсия. Сортировка слиянием. Восходящая сортировка слиянием. Сложность сортировки. Устойчивость сортировок, слайд №6

Рекурсия. Сортировка слиянием. Восходящая сортировка слиянием. Сложность сортировки. Устойчивость сортировок, слайд №7

Рекурсия. Сортировка слиянием. Восходящая сортировка слиянием. Сложность сортировки. Устойчивость сортировок, слайд №8

Рекурсия. Сортировка слиянием. Восходящая сортировка слиянием. Сложность сортировки. Устойчивость сортировок, слайд №9

Рекурсия. Сортировка слиянием. Восходящая сортировка слиянием. Сложность сортировки. Устойчивость сортировок, слайд №10

Рекурсия. Сортировка слиянием. Восходящая сортировка слиянием. Сложность сортировки. Устойчивость сортировок, слайд №11

Рекурсия. Сортировка слиянием. Восходящая сортировка слиянием. Сложность сортировки. Устойчивость сортировок, слайд №12

Рекурсия. Сортировка слиянием. Восходящая сортировка слиянием. Сложность сортировки. Устойчивость сортировок, слайд №13

Рекурсия. Сортировка слиянием. Восходящая сортировка слиянием. Сложность сортировки. Устойчивость сортировок, слайд №14

Рекурсия. Сортировка слиянием. Восходящая сортировка слиянием. Сложность сортировки. Устойчивость сортировок, слайд №15

Рекурсия. Сортировка слиянием. Восходящая сортировка слиянием. Сложность сортировки. Устойчивость сортировок, слайд №16

Рекурсия. Сортировка слиянием. Восходящая сортировка слиянием. Сложность сортировки. Устойчивость сортировок, слайд №17

Рекурсия. Сортировка слиянием. Восходящая сортировка слиянием. Сложность сортировки. Устойчивость сортировок, слайд №18

Рекурсия. Сортировка слиянием. Восходящая сортировка слиянием. Сложность сортировки. Устойчивость сортировок, слайд №19

Рекурсия. Сортировка слиянием. Восходящая сортировка слиянием. Сложность сортировки. Устойчивость сортировок, слайд №20

Рекурсия. Сортировка слиянием. Восходящая сортировка слиянием. Сложность сортировки. Устойчивость сортировок, слайд №21

Рекурсия. Сортировка слиянием. Восходящая сортировка слиянием. Сложность сортировки. Устойчивость сортировок, слайд №22

Рекурсия. Сортировка слиянием. Восходящая сортировка слиянием. Сложность сортировки. Устойчивость сортировок, слайд №23

Рекурсия. Сортировка слиянием. Восходящая сортировка слиянием. Сложность сортировки. Устойчивость сортировок, слайд №24

Рекурсия. Сортировка слиянием. Восходящая сортировка слиянием. Сложность сортировки. Устойчивость сортировок, слайд №25

Рекурсия. Сортировка слиянием. Восходящая сортировка слиянием. Сложность сортировки. Устойчивость сортировок, слайд №26

Рекурсия. Сортировка слиянием. Восходящая сортировка слиянием. Сложность сортировки. Устойчивость сортировок, слайд №27

Рекурсия. Сортировка слиянием. Восходящая сортировка слиянием. Сложность сортировки. Устойчивость сортировок, слайд №28

Рекурсия. Сортировка слиянием. Восходящая сортировка слиянием. Сложность сортировки. Устойчивость сортировок, слайд №29

Рекурсия. Сортировка слиянием. Восходящая сортировка слиянием. Сложность сортировки. Устойчивость сортировок, слайд №30

Рекурсия. Сортировка слиянием. Восходящая сортировка слиянием. Сложность сортировки. Устойчивость сортировок, слайд №31

Рекурсия. Сортировка слиянием. Восходящая сортировка слиянием. Сложность сортировки. Устойчивость сортировок, слайд №32

Рекурсия. Сортировка слиянием. Восходящая сортировка слиянием. Сложность сортировки. Устойчивость сортировок, слайд №33

Рекурсия. Сортировка слиянием. Восходящая сортировка слиянием. Сложность сортировки. Устойчивость сортировок, слайд №34

Рекурсия. Сортировка слиянием. Восходящая сортировка слиянием. Сложность сортировки. Устойчивость сортировок, слайд №35

Рекурсия. Сортировка слиянием. Восходящая сортировка слиянием. Сложность сортировки. Устойчивость сортировок, слайд №36

Рекурсия. Сортировка слиянием. Восходящая сортировка слиянием. Сложность сортировки. Устойчивость сортировок, слайд №37

Рекурсия. Сортировка слиянием. Восходящая сортировка слиянием. Сложность сортировки. Устойчивость сортировок, слайд №38

Рекурсия. Сортировка слиянием. Восходящая сортировка слиянием. Сложность сортировки. Устойчивость сортировок, слайд №39

Рекурсия. Сортировка слиянием. Восходящая сортировка слиянием. Сложность сортировки. Устойчивость сортировок, слайд №40

Рекурсия. Сортировка слиянием. Восходящая сортировка слиянием. Сложность сортировки. Устойчивость сортировок, слайд №41

Рекурсия. Сортировка слиянием. Восходящая сортировка слиянием. Сложность сортировки. Устойчивость сортировок, слайд №42

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Рекурсия. Сортировка слиянием. Восходящая сортировка слиянием. Сложность сортировки. Устойчивость сортировок. Доклад-сообщение содержит 42 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Рекурсия

Слайд 2

Описание слайда:

Пример бесконечной рекурсии У попа была собака, он её любил, Она съела кусок мяса, он её убил, В землю закопал, Надпись написал: У попа была собака, он её любил, Она съела кусок мяса, он её убил, В землю закопал, Надпись написал:

Слайд 3

Описание слайда:

Рекурсивная функция function arifmPr(base, iter: integer): integer; begin if iter = 1 then arifmPr:= base else arifmPr:= arifmPr(base, iter - 1) + base; end;

Слайд 4

Описание слайда:

Рекурсивная функция arifmPr(2, 4) arifmPr:= arifmPr(2,3)+2 arifmPr:= 8+2 arifmPr(2, 3) arifmPr:= arifmPr(2,2)+2 arifmPr:= 6+2 arifmPr(2, 3) arifmPr:= arifmPr(2,2)+2 arifmPr:= 4+2 arifmPr(2, 2) arifmPr:= arifmPr(2,1)+2 arifmPr:= 2+2 arifmPr(2, 1) arifmPr:= 2

Слайд 5

Описание слайда:

Сортировка слиянием (Mergesort)

Слайд 6

Описание слайда:

Два классических алгоритма сортировки Критические компоненты в мировой вычислительной инфраструктуре Понимание научных основ этих алгоритмов даст нам возможность разрабатывать прикладные системы для решения реальных задач Быстрая сортировка входит в десятку самых полезных алгоритмов, разработанных в 20-м веке

Слайд 7

Описание слайда:

Сортировка слиянием Основной план Разделить массив на две половины Рекурсивно отсортировать каждую половину Соединить две половины

Слайд 8

Описание слайда:

Сортировка слиянием Цель. Получить два отсортированных подмассива от a[lo] до a[mid] и от a[mid+1] до a[hi] Видео 1

Слайд 9

Описание слайда:

Слияние: реализация на Java

Слайд 10

Описание слайда:

Assertions Assertion. Оператор для тестирования программы Помогает обнаружить логические ошибки Документирует код Java assert оператор. Генерирует исключительную ситуацию, если условие не верно

Слайд 11

Описание слайда:

Сортировка слиянием: реализация на Java

Слайд 12

Описание слайда:

Сортировка слиянием: трассировка

Слайд 13

Описание слайда:

Видео 2 Видео 2

Слайд 14

Описание слайда:

Сортировка слиянием: эмпирический анализ Оценка времени выполнения: На ПК 108 сравнений/секунду На суперкомпьютере 1012 сравнений/секунду

Слайд 15

Описание слайда:

Сортировка слиянием: количество сравнений и обращений к массиву Утвержение. Сортировка слиянием использует NlogN сравнений и 6 NlogN обращений для сортировки массива размером N Доказательство. C(N) — количество сравнений, A(N) — количество обращений

Слайд 16

Описание слайда:

Разделяй и властвуй Утверждение. Если D(N) удовлетворяет D(N) = 2D(N/2) + N, где N > 1 и D(1) = 0, то D(N) = Nlog2N

Слайд 17

Описание слайда:

Разделяй и властвуй Утверждение. Если D(N) удовлетворяет D(N) = 2D(N/2) + N, где N > 1 и D(1) = 0, то D(N) = Nlog2N

Слайд 18

Описание слайда:

Разделяй и властвуй Утверждение. Если D(N) удовлетворяет D(N) = 2 D(N/2) + N, где N > 1 и D(1) = 0, то D(N) = Nlog2N

Слайд 19

Описание слайда:

Анализ сортировки слиянием: память Утверждение. Сортировка слиянием использует дополнительную память пропорциональную N Массиву aux[] нужен N ячеек для последнего слияния

Слайд 20

Описание слайда:

Сортировка слиянием: реализация Используйте сортировку вставками для маленьких подмассивов Сортировка слиянием очень дорогая для маленьких подмассивов Подмассивы для сортировки вставками ~ 7

Слайд 21

Описание слайда:

Сортировка слиянием: реализация Остановка если все отсортировано Если самый большой элемент первой половины

Слайд 22

Описание слайда:

Сортировка слиянием: реализация Ограничить копирование во вспомогательный массив Экономит время (но не память). Менять местами основной и вспомогательный массив при рекурсивном вызове

Слайд 23

Описание слайда:

Сортировка слиянием: визуализация

Слайд 24

Описание слайда:

Восходящая сортировка слиянием (Bottom-up mergesort)

Слайд 25

Описание слайда:

Восходящая сортировка слиянием Начинаем со слияния подмассивов с размером 1 Повторяем для подмассивов с размерами 2, 4, 8, 16, ...

Слайд 26

Описание слайда:

Восходящая сортировка слиянием: реализация на Java Итог. Простая и не рекурсивная версия сортировки слиянием (работает на 10% медленнее, чем нисходящая сортировка слиянием)

Слайд 27

Описание слайда:

Восходящая сортировка слиянием: визуализация

Слайд 28

Описание слайда:

Сложность сортировки

Слайд 29

Описание слайда:

Сложность сортировки Вычислительная сложность - основа для обучения эффективным алгоритмам для решения конкреной проблемы Х Вычислительная модель. Возможные операции Стоимость модели. Количество операций Верхняя граница. Стоимость, гарантированная определенным алгоритмам для задачи Х Нижняя граница. Доказанное ограничение стоимости для всех алгоритмов для задачи Х Оптимальный алгоритм. Алгоритм с лучшей максимально возможной стоимостью для задачи Х (когда верхняя и нижняя граница приблизительно совпадают) Пример: сортировка Вычислительная модель: дерево принятия решений Стоимость модели: количество сравнений Верхняя граница: ~ Nlog2N для сортировки слиянием Нижняя граница: ? Оптимальный алгоритм: ?

Слайд 30

Описание слайда:

Дерево принятия решений (для 3-х элементов)

Слайд 31

Описание слайда:

Нижняя граница для сортировки на основе сравнений Утверждение. Ни один алгоритм сортировки, основанный на сравнениях, не может гарантировать упорядочить N элементов, выполнив менее log2(N!) ~ Nlog2(N) сравнений Доказательство Все элементы массива различны В худшем случае высота дерева будет h Бинарное дерево высотой h имеет максимум 2h листьев N!

Слайд 32

Описание слайда:

Слайд 33

Описание слайда:

Сложность сортировки Вычислительная модель. Возможные операции Стоимость модели. Количество операций Верхняя граница. Стоимость, гарантированная определенным алгоритмам для задачи Х Нижняя граница. Доказанное ограничение стоимости для всех алгоритмов для задачи Х Оптимальный алгоритм. Алгоритм с лучшей максимально возможной стоимостью для задачи Х (когда верхняя и нижняя граница приблизительно совпадают) Пример: сортировка Вычислительная модель: дерево принятия решений Стоимость модели: количество сравнений Верхняя граница: ~ Nlog2N для сортировки слиянием Нижняя граница: ~ Nlog2N Оптимальный алгоритм: сортировка слиянием Первая цель разработки алгоритмов: оптимальный алгоритм

Слайд 34

Описание слайда:

Сложность сортировки Сравнения? Сортировка слиянием оптимальна по количеству сравнений Память? Сортировка слиянием не оптимальна по памяти

Слайд 35

Описание слайда:

Сложность сортировки Можно снизить нижнюю границу для сортировки если есть информация о: Упорядоченности входных данных Распределении значений ключей Представлении ключей Частично-упорядоченный массив Дубликаты ключей. Зная распределение дубликатов во входных данных, мы можем отказаться от NlogN Представление ключей. Можем использовать цифровые/символьные сравнения ключей вместо сравнений номеров и строк