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

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
Рекурсия. Сортировка слиянием. Восходящая сортировка слиянием. Сложность сортировки. Устойчивость сортировок, слайд №1Рекурсия. Сортировка слиянием. Восходящая сортировка слиянием. Сложность сортировки. Устойчивость сортировок, слайд №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;
Описание слайда:
Рекурсивная функция 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
Описание слайда:
Рекурсивная функция 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)
Описание слайда:
Сортировка слиянием (Mergesort)

Слайд 6


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

Слайд 7


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

Слайд 8


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

Слайд 9


Слияние: реализация на Java
Описание слайда:
Слияние: реализация на Java

Слайд 10


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

Слайд 11


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

Слайд 12


Сортировка слиянием: трассировка
Описание слайда:
Сортировка слиянием: трассировка

Слайд 13


Видео 2 Видео 2
Описание слайда:
Видео 2 Видео 2

Слайд 14


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

Слайд 15


Сортировка слиянием: количество сравнений и обращений к массиву Утвержение. Сортировка слиянием использует NlogN сравнений и 6 NlogN обращений для сортировки массива размером N Доказательство. C(N) — количество сравнений, A(N) — количество обращений
Описание слайда:
Сортировка слиянием: количество сравнений и обращений к массиву Утвержение. Сортировка слиянием использует 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
Описание слайда:
Разделяй и властвуй Утверждение. Если 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
Описание слайда:
Разделяй и властвуй Утверждение. Если 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
Описание слайда:
Разделяй и властвуй Утверждение. Если D(N) удовлетворяет D(N) = 2 D(N/2) + N, где N > 1 и D(1) = 0, то D(N) = Nlog2N

Слайд 19


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

Слайд 20


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

Слайд 21


Сортировка слиянием: реализация Остановка если все отсортировано Если самый большой элемент первой половины <= самому маленькому элементу второй половины, то подмассив отсортирован Полезно для частично-упорядоченного массива
Описание слайда:
Сортировка слиянием: реализация Остановка если все отсортировано Если самый большой элемент первой половины <= самому маленькому элементу второй половины, то подмассив отсортирован Полезно для частично-упорядоченного массива

Слайд 22


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

Слайд 23


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

Слайд 24


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

Слайд 25


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

Слайд 26


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

Слайд 27


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

Слайд 28


Сложность сортировки
Описание слайда:
Сложность сортировки

Слайд 29


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

Слайд 30


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

Слайд 31


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

Слайд 32


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

Слайд 33


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

Слайд 34


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

Слайд 35


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

Слайд 36


Устойчивость сортировок
Описание слайда:
Устойчивость сортировок

Слайд 37


Устойчивость Типичная задача. Отсортировать сначала по имени, а затем, по группам
Описание слайда:
Устойчивость Типичная задача. Отсортировать сначала по имени, а затем, по группам

Слайд 38


Устойчивость Сортировка вставками и сортировка слиянием устойчивы (но не выборочная и Шелла)
Описание слайда:
Устойчивость Сортировка вставками и сортировка слиянием устойчивы (но не выборочная и Шелла)

Слайд 39


Устойчивость: сортировка вставками Сортировка вставками устойчива Равные элементы не передвигаются
Описание слайда:
Устойчивость: сортировка вставками Сортировка вставками устойчива Равные элементы не передвигаются

Слайд 40


Устойчивость: выборочная сортировка Выборочная сортировка не устойчива Передвижения элементов на большие расстояния может нарушить порядок
Описание слайда:
Устойчивость: выборочная сортировка Выборочная сортировка не устойчива Передвижения элементов на большие расстояния может нарушить порядок

Слайд 41


Устойчивость: сортировка Шелла Сортировка Шелла не устойчива Передвижения элементов на большие расстояния может нарушить порядок
Описание слайда:
Устойчивость: сортировка Шелла Сортировка Шелла не устойчива Передвижения элементов на большие расстояния может нарушить порядок

Слайд 42


Устойчивость: сортировка слиянием Сортировка слиянием устойчива Если ключи равны, то берутся элементы из левого подмассива
Описание слайда:
Устойчивость: сортировка слиянием Сортировка слиянием устойчива Если ключи равны, то берутся элементы из левого подмассива

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию