Частичное упрядочение - презентация, доклад, проект скачать

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

Содержание ▲

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

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

Слайд 1

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

Структуры и алгоритмы обработки данных, 2 Лекция 6 Частичное упрядочение Частичный порядок Алгоритм выбора k-го элемента на основе процедуры разделения Partition Линейный алгоритм выбора k-го элемента

Слайд 2

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

Частичный порядок

Слайд 3

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

Выбор k-го элемента Синонимы: порядковые статистики, ранги, ранговые статистики Даны: список из n элементов и натуральное число k. Требуется: найти элемент, который в отсортированном в возрастающем порядке списке занимал бы k-ую позицию. Более точно – получить Sn-kk-1

Слайд 4

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

Выбор k-го элемента Алгоритм на основе процедуры Partition

Слайд 5

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

Алгоритм на основе процедуры Partition

Слайд 6

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

Алгоритм на основе процедуры Partition Анализ алгоритма Благоприятный случай – деление пополам

Слайд 7

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

Линейный алгоритм выбора k-го элемента

Слайд 8

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

Линейный алгоритм выбора k-го элемента Состояние после 2-го шага

Слайд 9

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

Линейный алгоритм выбора k-го элемента Шаг 3. «Разбрасываем» 6q элементов из C + D относительно медианы медиан (ММ). Каждая тройка распределяется за 2 сравнения. Всего имеем 4q действий: 4q  2(2q +1)=(2/7)n Оценим размеры правой и левой частей относительно ММ. A’=A+ (добавка из C + D ) B’=B+ (добавка из C + D ) Максимальный размер A’ или B’ равен (4q + 3) + (6q) = 10q + 3 Остальные элементы (4q + 4) «отсекаются» на шаге 4. 10q + 3  10q + 5 = 5(2q +1)=(5/7)n

Слайд 10

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

Линейный алгоритм выбора k-го элемента Шаг 4. Рекурсивный вызов «вправо» или «влево» от ММ При номер(ММ) > k  выбор из сегмента L..ММ1 При номер(ММ) < k  выбор из сегмента ММ+1..R При номер(ММ) = k  Return Стоимость шага 4 есть T ( (5/7)n ) Итак общий баланс по всем 4-м шагам:

Слайд 11

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

Линейный алгоритм выбора k-го элемента

Слайд 12

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

Линейный алгоритм выбора k-го элемента Этот алгоритм лучше, чем прямая сортировка, при n > 210. При разбиении на «пятерки» получили бы T(n)  18n. Общий метод (проектная модель) разработки алгоритмов Prune & Search или Отсечение и Поиск