|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[61] Рис. 10.1 Анализ алгоритма select. Элементы массива (их п) изображены кружками, каждый столбец - группа из 5 или меньше элементов, белые кружки - медианы групп. «Медиана медиан» обозначена буквой х. Стрелки идут от больших чисел к меньшим. Видно, что в каждом из полных столбцов правее х имеется три числа, больших х, и что в каждом из столбцов левее х имеется три числа, меньших х. Множество чисел, заведомо больших х, выделено серым. Пусть теперь Т{п) - время работы алгоритма Select на массиве из га элементов в худшем случае. Первый, второй и четвертый шаги выполняются за время О (га) (на втором шаге мы О (га) раз сортируем массивы размером 0(1)), третий шаг выполняется за время не более Т([га/5]), а пятый шаг, по доказанному, - за время, не превосходящее Т([7га/10 + 6]) (как и раньше, можно предполагать, что Т(п) монотонно возрастает с ростом га). Стало быть, Т(га) Т(\п/5]) + Т([7га/10 + 6J) + 0(п). Поскольку сумма коэффициентов при га в правой части (1/5 + 7/10 = 9/10) меньше единицы, из этого рекуррентного соотношения вытекает, что Т{п) era для некоторой константы с. Это можно доказать по индукции. В самом деле, предполагая, что T(m) сто для всех то < га, имеем Т(га) с(\п/5]) + с([7га/10 + 6j) + 0(п) с(п/5 + 1) + с(7га/10 + 6) + 0(п) 9сга/10 + 7с+О(га) = = сп - с(га/10 - 7) + 0(п). При подходящем выборе с это выражение будет не больше сп при всех га > 70 (надо, чтобы с(га/10 - 6) превосходило коэффициент, подразумеваемый в О(п)). Таким образом, индуктивный переход возможен при га > 70 (заметим ещё, что при таких га выражения [га/5] и [7га/10 + 6] меньше га). Увеличив с ещё (если надо), можно добиться того, чтобы Т{п) не превосходило era и при всех га 70, что завершает рассуждение по индукции. Стало быть, алгоритм Select работает за линейное время (в худшем случае). Отметим, что алгоритмы Select и Randomized-Select, в отличие от описанных в главе 9 алгоритмов сортировки за линейное время, используют только попарные сравнения элементов массива и применимы для произвольного упорядоченного множества. Эти алгоритмы асимптотически эффективнее очевидного подхода «упорядочи множество и выбери нужный элемент», поскольку всякий алгоритм сортировки, использующий только попарные сравнения, требует времени fi(ralgra) не только в худшем случае (раздел 9.1), но и в среднем (задача 9-1). Упражнения 10.3-1 Будет ли алгоритм Select работать за линейное время, если разбивать массив на группы не из пяти, а из семи элементов? Покажите, что для групп из трёх элементов рассуждение не проходит. 10.3-2 Пусть х - «медиана медиан» в алгоритме Select (массив содержит га элементов). Покажите, что при га 38 количество элементов, больших х (так же как и количество элементов, меньших х) не меньше [~га/4]. 10.3-3 Модифицируйте алгоритм быстрой сортировки так, чтобы он работал за время О (га lgra) в худшем случае. 10.3-4* Пусть алгоритм выбора г-го по счёту элемента использует только попарные сравнения. Покажите, что с помощью тех же сравнений можно в качестве побочного результата получить списки элементов, меньших искомого, а также больших искомого. 10.3-5 Пусть у нас есть какой-то алгоритм, находящий медиану за линейное в худшем случае время. Используя его в качестве подпрограммы, разработайте простой алгоритм, решающий задачу нахождения произвольной порядковой статистики за линейное время. 10.3-6 Под /г-квантилями (A;-th quantiles) множества из га чисел мы понимаем к - 1 его элементов, обладающих следующим свойством: если расположить элементы множества в порядке возрастания, то квантили будут разбивать множество на к равных (точнее, отличающихся не более чем на один элемент) частей. Разработайте алгоритм, который за время O(ralgfc) находит /г-квантили данного множества. 10.3-7 Разработайте алгоритм, который по заданному к находит в данном множестве S его к элементов, менее всего отстоящих от медианы. Число операций должно быть 0(15*1). Рис. 10.2 Как провести с востока на запад магистраль, чтобы суммарная длина подводящих трубопроводов была минимальна? 10.3-8 Пусть Х[1..га] и У[1..га] - два возрастающих массива. Разработайте алгоритм, находящий за время O(lgra) медиану множества, полученного объединением элементов этих массивов. 10.3-9 Профессор консультирует нефтяную компанию, которой требуется провести магистральный нефтепровод в направлении строго с запада на восток через нефтеносное поле, на котором расположены га нефтяных скважин. От каждой скважины необходимо подвести к магистрали трубопровод по кратчайшему пути (строго на север или на юг, рис. 10.2). Координаты всех скважин профессору известны; необходимо выбрать местоположение магистрали, чтобы сумма длин всех трубопроводов, ведущих от скважин к магистрали, была минимальна. Покажите, что оптимальное место для магистрали можно найти за линейное время. Задачи 10-1 Сортировка г наибольших элементов Дано множество из га чисел; требуется выбрать из них г наибольших и отсортировать (пользуясь только попарными сравнениями). Для каждого из приведенных ниже подходов разработайте соответствующий алгоритм и выясните, как зависит от га и г время работы этих алгоритмов в худшем случае. а.Отсортировать все числа и выписать г наибольших. б.Поместить числа в очередь с приоритетами и вызвать г раз процедуру Extract-Max. |
Среды: 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 | ||