|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[48] Задачи к главе 7 153 7.5-6 Придумайте алгоритм, который позволяет за время О (nig/г) слить к отсортированных списков в один отсортированный список (здесь п - общее число элементов в списках). (Указание: используйте кучу.) Задачи 7-1 Построение кучи с помощью вставок Можно построить кучу, последовательно добавляя элементы с помощью процедуры Heap-Insert. Рассмотрим следующий алгоритм: Build-Heap(A) 1heap-size[A] <- 1 2for г f- 2 to length[A] 3do Heap-Insert (A, A[i]) а.Запустим процедуры Build-Heap и Build-Heap для одного и того же массива. Всегда ли они создадут одинаковые кучи? (Докажите или приведите контрпример.) б.Докажите, что время работы процедуры Build-Heap в худшем случае составляет О (га lgra) (где га - количество элементов). 7-2 Работа с d-ичными кучами Рассмотрим d-ичную кучу (d-агу heap), в которой вершины имеют d детей вместо двух. а.Как выглядят для такой кучи процедуры, аналогичные Parent, Left и Right? б.Как высота d-ичной кучи из га элементов выражается через га и dt в.Реализуйте процедуру Extract-Max. Каково время её работы (выразите его через га и d)l г.Реализуйте процедуру Insert. Каково время её работы? д.Реализуйте процедуру Heap-Increase-Key (упр. 7.5-4). Каково время её работы? Замечания Алгоритм сортировки с помощью кучи предложил Уильяме [202]; там же описана реализация очереди с приоритетами на базе кучи. Процедура Build-Heap предложена Флойдом [69]. 8 Быстрая сортировка В этой главе рассмотрен так называемый алгоритм «быстрой сортировки». Хотя время его работы для массива из га чисел в худшем случае составляет ©(га2), на практике этот алгоритм является одним из самых быстрых: математическое ожидание времени работы составляет в (га lgra), причём множитель при ralgra довольно мал. Кроме того, быстрая сортировка не требует дополнительной памяти и сохраняет эффективность для систем с виртуальной памятью. В разделе 8.1 описывается алгоритм в целом и процедура разделения массива на части. Оценка эффективности алгоритма довольно сложна; в разделе 8.2 приводятся интуитивные доводы, а строгий анализ отложен до раздела 8.4. В разделе 8.3 описаны варианты быстрой сортировки, использующие генератор случайных чисел. При этом время работы в худшем случае (при неудачном случайном выборе) составляет О (га2), но среднее время работы составляет лишь О (га lgra). (Говоря о среднем времени, мы имеем в виду не усреднение по всем входам, а математическое ожидание времени работы, которое для любого входа не превосходит O(ralogra).) Один из вариантов вероятностного алгоритма быстрой сортировки подробно анализируется в разделе 8.4, где доказаны оценки для среднего и наибольшего времени работы. 8.1. Описание быстрой сортировки Быстрая сортировка (quicksort), как и сортировка слиянием, основана на принципе «разделяй и властвуй» (см. разд. 1.3.1). Сортировка участка А\р . .г] происходит так: •Элементы массива А переставляются так, чтобы любой из элементов А\р],..., A[q] был не больше любого из элементов 1],..., А[г], где q - некоторое число в интервале р q < г. Эту операцию мы будем называть разделением (partition). •Процедура сортировки рекурсивно вызывается для массивов А\р .. q] и A[q + 1.. г]. После этого массив А\р . .г] отсортирован. Итак, процедура сортировки Quicksort выглядит следующим образом: Quicksort(A, р, г) 1if р < г 2then q +- Partition (А, р, г) 3Quicksort(A,p, q) 4Quicksort(A, q + 1, г) Для сортировки всего массива необходимо выполнить процедуру Quicksort А, 1, length[A]). Разбиение массива Основной шаг алгоритма - процедура Partition, которая переставляет элементы массива А\р. .г] нужным образом: Partition(А, р, г) 1ж <г- А[р] 2г +- р - 1 3jf-r + 1 4while true 5do repeat j <- j - 1 6until A[j] ж 7repeat г <- г -\- 1 8until A[i] x 9if г < j 10then поменять A[i] f+ A[j] 11else return j Работа процедуры Partition показана на рис. 8.1. Элемент х = А\р] выбирается в качестве «граничного»; массив А\р. .q] будет содержать элементы, не большие ж, а массив A[g+1.. г] - элементы, не меньшие ж. Идея состоит в том, чтобы накапливать элементы, не большие ж, в начальном отрезке массива (А[р. л]), а элементы, не меньшие ж - в конце (A[j. .г]). В начале оба «накопителя» пусты: г = р - l,j = r+ l. Внутри цикла while (в строках 5-8) к начальному и конечному участкам присоединяются элементы (как минимум по одному). После выполнения этих строк А [г] ж АЦ]. Если мы поменяем А [г] и A[j] местами, то их можно будет присоединить к начальному и конечному участкам. В момент выхода из цикла выполнено неравенство г j. При этом массив разбит на части А[р],..., A[j] и A[j + 1],..., А [г]; любой элемент первой части не превосходит любого элемента второй |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||