|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[5] sorted sequence - отсортированная последовательность merge - слияние initial sequence - начальная последовательность Рис. 1.3 Сортировка слиянием для массива А = (5, 2, 4, 6, 1, 3, 2, 6). Весь массив теперь можно отсортировать с помощью вызова Merge-Sort(A, 1, length[A]). Если длина массива га = length[A] есть степень двойки, то в процессе сортировки произойдёт слияние пар элементов в отсортированные участки длины 2, затем слияние пар таких участков в отсортированные участки длины 4 и так далее до га (на последнем шаге соединяются два отсортированных участка длины га/2). Этот процесс показан на рис. 1.3. 1.3.2. Анализ алгоритмов типа «разделяй и властвуй» Как оценить время работы рекурсивного алгоритма? При подсчёте мы должны учесть время, затрачиваемое на рекурсивные вызовы, так что получается некоторое рекуррентное соотношение (recurrence equation). Далее следует оценить время работы, исходя из этого соотношения. Вот примерно как это делается. Предположим, что алгоритм разбивает задачу размера га на а подзадач, каждая из которых имеет в Ь раз меньший размер. Будем считать, что разбиение требует времени D(n), а соединение полученных решений - времени С(га). Тогда получаем соотношение для времени работы Т{п) на задачах размера га (в худшем случае): Т{п) = аТ(п/Ь) + D(n) + С(га). Это соотношение выполнено для достаточно больших га, когда задачу имеет смысл разбивать на подзадачи. Для малых га, когда такое разбиение невозможно или не нужно, применяется какой-то прямой метод решения задачи. Поскольку га ограничено, время работы тоже не превосходит некоторой константы. Анализ сортировки слиянием Для простоты будем предполагать, что размер массива (га) есть степень двойки. (Как мы увидим в главе 4, это не очень существенно.) Тогда на каждом шаге сортируемый участок делится на две равные половины. Разбиение на части (вычисление границы) требует времени ©(1), а слияние - времени О(га). Получаем соотношение Как мы увидим в главе 4, это соотношение влечёт Т{п) = в (га log га), где через log мы обозначаем двоичный логарифм (основание логарифмов, впрочем, не играет роли, так как приводит лишь к изменению константы). Поэтому для больших га сортировка слиянием эффективнее сортировки вставками, требующей времени 0(га2). Упражнения 1.3-1 Следуя образцу рис. 1.3, показать работу сортировки слиянием для массива А = (3, 41, 52, 26, 38, 57, 9,49). 1.3-2 Написать текст процедуры Merge (А, р, q, г). 1.3-3 Докажите по индукции, что если то Т(п) = га log га (при всех га, являющихся степенями двойки). 1.3-4 Сортировку вставками можно оформить как рекурсивную процедуру: желая отсортировать А[1. .га], мы (рекурсивно) сортируем А[1. .га - 1], а затем ставим А[п] на правильное место в отсортированном массиве А[1. .га - 1]. Напишите рекуррентное соотношение для времени работы такой процедуры. если га = 1 2,если га = 2, 1.3-5 Возвращаясь к задаче поиска (упр. 1.1-3), заметим, что при поиске в отсортированном массиве мы можем сначала сравнить искомый элемент со средним элементом массива, узнать, в какой половине его следует искать, а затем применить ту же идею рекурсивно. Такой способ называется двоичным поиском (binary search). Напишите соответствующую программу, используя цикл или рекурсию. Объясните, почему время её работы есть О (log га). 1.3-6 Заметим, что цикл while в строках 5-7 процедуры Insertion-Sort (разд. 1.1) просматривает элементы отсортированного участка А[1. .j - 1] подряд. Вместо этого можно было бы использовать двоичный поиск (упр. 1.3-5), чтобы найти место вставки за время О (log га). Удастся ли таким образом сделать общее время работы равным ©(га log га)? 1.3-7* Дан массив S из га действительных чисел, а также число х. Как за время ©(ralogra) определить, можно ли представить х в виде суммы двух элементов массива S? Замечания Как мог бы сказать Козьма Прутков, хороший алгоритм подобен острому ножу - тот и другой достигают цели легко и просто. Другое сравнение: человек, пользующийся плохим алгоритмом, подобен повару, отбивающему мясо отвёрткой: едва съедобный и малопривлекательный результат достигается ценой больших усилий. Часто разница между плохим и хорошим алгоритмом более существенна, чем между быстрым и медленным компьютером. Пусть мы хотим отсортировать массив из миллиона чисел. Что быстрее - сортировать его вставками на суперкомпьютере (100 миллионов операций в секунду) или слиянием на домашнем компьютере (1 миллион операций)? Пусть к тому же сортировка вставками написана на ассемблере чрезвычайно экономно, и для сортировки га чисел нужно, скажем, лишь 2га2 операций. В то же время алгоритм слиянием написан без особой заботы об эффективности и число операций есть 50га log га. Для сортировки миллиона чисел получаем 10 операций в секунду для домашнего компьютера. Мы видим, что разработка эффективных алгоритмов - не менее важная компьютерная технология, чем разработка быстрой электроники. В этой области также происходит заметный прогресс. 20 000 секунд рй 5,56 часов 10 операций в секунду для суперкомпьютера и всего операции 1 000 секунд рй 17 минут |
Среды: 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 | ||