Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 36
Текст из файла (страница 36)
В задаче предполагается, что число пзь, достаточно большое, чтобы вероятностью переполнения можно было пренебречь. и Покажите, что математическое ожидание значения счетчика после применения к нему и операций 1исккмкнт равно и. б. Анализ дисперсии значения счетчика зависит от выбора последовательности пь Рассмотрим простой случай, когда и; = 1001 для всех 1 > О. Оцените дисперсию значения счетчика после выполнения операции 1исккмкггт и раз. 5.2. Поиск в неотсортированном массиве В этой задаче исследуются три алгоритма поиска значения х в неотсортированном и-элементном массиве А. Рассмотрим следующую рандомизированную стратегию: выбираем элемент массива А с произвольным индексом г' и проверяем справедливость равенства А!ь] = х.
Если оно выполняется, то алгоритм завершается. В противном случае продолжаем поиск, случайным образом выбирая новые элементы массива А. Перебор индексов продолжается до тех пор, пока не будет найден такой индекс 5, что АЦ = х, или пока не будут проверены все элементы массива. Заметим, что выбор каждый раз производится среди всех индексов массива, поэтому круг поиска не сужается и один и тот же элемент может проверяться неоднократно.
а. Напишите псевдокод процедуры Клипом-Бклксн, реализующей описанную стратегию. Позаботьтесь, чтобы алгоритм прекращал работу после того, как будут проверены все индексы массива. б. Предположим, что имеется ровно один индекс г, такой, что А[с) = х. Чему равно математическое ожидание количества индексов в массиве А, которые 171 Глава 5.
Вероятностный аналоя и рандомизированные алгоритмы будут проверены до того, как будет найден элемент х и процедура КАмпом- БВАксн завершит работу? ж Обобщите решение сформулированной в п. (б) задачи для ситуации, когда имеются к > 1 индексов 1, таких, что А[() = х. Чему равно математическое ожидание количества индексов в массиве А, которые будут проверены до того, как будет найден элемент х и процедура КАмпом-БВАксн завершит работу? Ответ должен представлять собой функцию от величин п и Й. * Предположим, что условие А[1] = х пе выполняется ии для какого индекса г? Чему равно математическое ожидание количества индексов в массиве А, которые придется проверить до того, как будут проверены все элементы массива и процедура КАмпом-БВАксн завершит работу? Теперь рассмотрим детерминированный алгоритм линейного поиска Рктпкм1м1зт1с-БВАксн.
В этом алгоритме поиск элемента х производится путем последовательной проверки элементов А[1), А[2], А[3],..., А(п] до тех пор, пока ие произойдет одно из двух событий: либо будет найден элемент А[(] = х, либо будет достигнут конец массива. Предполагается, что все возможные перестановки элементов входного массива встречаются с одииаковой вероятностью. д. Предположим, что имеется всего один индекс 1, такой, что А[1] = х. Чему равно время работы процедуры Рктпкм1м1зт1с-Бклксн в среднем случае? Как ведет себя эта величина в наихудшем случае? е. Обобщите решение сформулированной в п.
(д) задачи для ситуации, когда имеются к > 1 индексов 1, для которых А[1) = х. Чему равно время работы процедуры Рптпкм1м1зт1с-БВАксн в среднем случае? Как ведет себя эта величина в наихудшем случае? Ответ должен быть функцией от п и к. ж. Предположим, что условие А[1) = х ие выполняется ии для какого элемеита массива А. Чему равно время работы процедуры Ретпкм1м1ят1с-ББАксн в среднем случае? Как ведет себя эта величина в наихудшем случае? Наконец рассмотрим раидомизироваииый алгоритм Бсклмвьк-БВлксн, в котором сначала выполняется случайная перестановка элементов входного массива, а затем в полученном массиве выполняется описанный выше линейный детермииироваииый поиск.
з. Пусть lс — количество индексов 1, таких, что А[() = х. Определите математическое ожидание времени работы процедуры Бсклмвьп-Бплксн и время ее работы в наихудшем случае для значений?с = 0 и к = 1. Обобщите решение для случая (с > 1. и. Какой из трех представленных алгоритмов вы бы предпочли? Поясните свой ответ. 177 часть в Осиови Заключнтельньзе замечания Описание большого количества усовершенствованных вероятностных методов можно найти в книгах Боллобаса (ВойоЬаз) [52], Гофри (Нойз) [173] и лекциях Спенсера (Ярепсег) [319].
Обзор и обсуждение преимуществ рандомизированных алгоритмов представлен в работах Карпа (Кщр) [199] и Рабина (КаЬ(п) [286]. Кроме того, рандомизированные алгоритмы подробно рассмотрены в учебнике Мотвани (Моплап() и Рагхтвагана (Ка8Ьгчайап) [260]. Различные варианты задачи о найме изучались многими исследователями. Этот класс задач более известен как "задачи о секретарях". Примером работы в этой области является статья Айтаи (А)за(), Меггидо (Ме881до) и Ваартса (%вана) [11]. 11 Сортировка и порядковая статистика Введение В этой части представлено несколько алгоритмов, с помощью которых можно решить следующую задачу сортыровки. Вход. Последовательность из и чисел (ан аз,..., а„). Выход.
Перестановка (переупорялочение) (а',, аз, ..., а'„) входной последовательности, такая, что а', < аз « ... а'„. Входная последовательность обычно имеет вид и-злементного массива, хотя мо- жет иметь и другое представление, например в виде связанного списка. Структура данных На практике сортируемые числа редко являются изолированными значениями. Обычно каждое из ннх входит в состав набора данных, который называется записью (гесоп)).
В каждой записи содержится ключ (йеу), представляющий собой соргируемое значение, в то время как остальная часть записи состоит из сопуюсювуюпгих данных, дополняющих ключ. Алгоритм сортировки на практике должен быть реализован так, чтобы он вместе с ключами переставлял и сопутствующие данные. Если каждая запись включает в себя сопутствующие данные большого объема, то с целью свести к минимуму перемещение данных сортировка часто проводится не в исходном массиве, а в массиве указателей на записи.
В определенном смысле сделанное вьппе замечание относится к особенностям реализации, отличающим алгоритм от конечной программы. Алгоритм сортировки описывает метод определения порядка сортировки вне зависимости от того, сортируются ли отдельные числа или большие записи с многобайтовымн сопутствующими данными. Таким образом, если речь идет о задаче сортировки, обычно предполагается, что входные данные состоят только из чисел. Преобразование алгоритма, предназначенного для сортировки чисел, в программу для сортировки записей не представляет концептуальных трудностей, хотя в конкретной Часть Рп Сортировка и оориоковаи статистика ! 75 практической ситуации иногда могут возникнуть нюансы, усложняющие задачу программиста.
Почему сортировка? Многие ученые в области вычислительной техники рассматривают сортировку как наиболее фундаментальную задачу при изучении алгоритмов. Тому есть несколько причин. Иногда в приложении не обойтись без сортировки информации. Например, чтобы подготовить отчет о состоянии счетов клиентов, банку необходимо выполнить сортировку чеков по их номерам. Часто в алгоритмах сортировка используется в качестве ключевой подпрограммы. Например„программе, выполняющей визуализацию перекрывающихся графических объектов, которые находятся на разных уровнях, сначала может понадобиться отсортировать эти объекты по уровням "снизу вверх", чтобы установить порядок их вывода.
В этой книге мы ознакомимся с многочисленными алгоритмами, в которых сортировка используется в качестве подпрограммы. Имеется большой выбор алгоритмов сортировки, в которых применяются самые разные технологии. Фактически в алгоритмах сортировки используются многие важные методы (зачастую разработанные еще на заре компьютерной эры), применяемые при разработке различных классов алгоритмов. В этом отношении задача сортировки представляет также исторический интерес. Можно доказать наличие нетривиальной нижней границы для задачи сортировки (что будет сделано в главе 8). Наши наилучшие верхние границы в асимптотическом пределе совпадают с нижней границей, что дает возможность заключить, что наши алгоритмы сортировки являются асимптотически оптимальными.
Кроме того, нижние оценки алгоритмов сортировки можно использовать для поиска нижних границ в некоторых других задачах. В процессе реализации алгоритмов сортировки на передний план выходят многие прикладные проблемы. Выбор наиболее производительной программы сортировки в той или иной ситуации может зависеть от многих факторов, таких как предварительные знания о ключах и сопутствующих данных, об иерархической организации памяти компьютера (наличии кеша и виртуальной памяти) и программной среды. Многие из этих вопросов лучше решать на уровне алгоритмов, а не "настройкой" кода.
Алгоритмы сортировки В главе 2 мы познакомили вас с двумя алгоритмами для сортировки и действительных чисел. Сортировка методом вставок в наихудшем случае выполняется за время 6(пз). Несмотря на далеко не самое оптимальное асимптотическое поведение этого алгоритма, благодаря компактности его внутренних циклов он быстро справляется с сортировкой массивов с небольшим количеством элементов ина 17б Часть 11. Сортировка и лорядттая статистика месте" (без привлечения дополнительной памяти, т.е. без выделения отдельного массива для работы и хранения выходных данных). (Напомним, что выполнение сортировки иа месте означает, что алгоритму требуется только определенное постоянное количество элементов вне исходного массива.) Сортировка методом слияния имеет асимптотически лучшее время работы ео(п 18 и), но процедура Мекая, которая используется в этом алгоритме, не работает без дополнительной памяти.
В этой части вы ознакомитесь еше с двумя алгоритмами, предназначенными для сортировки произвольных действительных чисел. Представленная в главе 6 пирамидальная сортировка позволяет отсортировать на месте п чисел за время 0(п!8 и). В ней используется важная структура данных, именуемая пирамидой (Ьеар), которая позволяет также реализовать очередь с приоритетами.
Рассмотренный в главе 7 алгоритм быстрой сортировки также сортирует п чисел ана месте", но время его работы в наихудшем случае равно 9(пз). Тем не менее его ожидаемое время работы — 9(п18п), и на практике по производительности он превосходит алгоритм пирамидальной сортировки. Код алгоритма быстрой сортировки такой же компактный, как и код алгоритма сортировки вставкой, поэтому скрытый постоянный множитель, влияющий на величину времени работы этого алгоритма, довольно мал.
Алгоритм быстрой сортировки приобрел широкую популярность для сортировки больших входных массивов. Сортировки вставкой, слиянием, пирамидальная и быстрая имеют одну общую особенность — все они работают по принципу попарного сравнения элементов входного массива. В начале главы 8 рассматривается модель дерева принятия решения, позволяюШая изучить ограничения производительности, присущие алгоритмам данного типа. С помощью этой модели доказывается, что в наихудшем случае нижняя оценка, ограничивакнцая время работы любого алгоритма, работающего методом сравнения, равна Й(п 18 и). Это означает, что алгоритмы пирамидальной сортировки и сортировки слиянием являются асимптотически оптимальными.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
