Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 34
Текст из файла (страница 34)
Чему равно математическое ожидание количества индексов в массиве А, которые придется проверить до того, как будут проверены все элементы и процедура Клнп0м БеАксн завершит работу? Теперь рассмотрим детерминированный алгоритм линейного поиска Рвтвкм~~т[с БвАксн. В этом алгоритме поиск элемента х производится путем последовательной проверки элементов А [1], А (2],..., А [и] до тех пор, пока не произойдет одно из двух событий: либо будет найден элемент А [г] = х, либо будет достигнут конец массива.
Предполагается, что все возможные перестановки элементов входного массива встречаются с одинаковой вероятностью. д) Предположим, что имеется всего один индекс г, такой что А [г] = х. Чему равно математическое ожидание времени работы процедуры Рвтвкм~ьлзт1с ЗвАксн? Как ведет себя эта величина в наихудшем случае? е) Обобщите решение сформулированной в части д задачи, при условии, что имеется й ) 1 индексов г, для которых А [1] = х. Чему равно математическое ожидание времени работы процедуры Ретекм1н|зт!с Бвлксн? Как ведет себя эта величина в наихудшем случае? Ответ должен зависеть от величин п и Й.
ж) Предположим, что условие А [1] = х не выполняется ни для какого элемента массива А. Чему равно математическое ожидание времени работы процедуры Рвтвкмпязт~с Бвлксн? Как ведет себя эта величина в наихудшем случае? Наконец, рассмотрим рандомизированный алгоритм ЯскАмвьв ЗвАксн, в котором сначала выполняется случайная перестановка элементов входного массива, а затем в полученном массиве выполняется описанный выше линейный детерминированный поиск.
з) Пусть )с — количество индексов 1, таких что А [1] = х. Определите математическое ожидание времени работы процедуры Зсклмвсв Бвлксн и время ее работы в наихудшем случае для значений й = 0 и /с = 1. Обобщите решение для случая й > 1. и) Какой из трех представленных алгоритмов вы бы предпочли? Объясните свой ответ. Глава 5..Вероятностный анализ и рандомизированные алгоритмы 171 Заключительные замечания Описание большого количества усовершенствованных вероятностных методов можно найти в книгах Боллобаса (Во11оЪаз) [44], Гофри (НоЫ) [151] и лекциях Спенсера (Брепсег) [283]. Обзор и обсуждение преимуществ рандомизированных алгоритмов представлен в работах Карпа (Катр) [174] и Рабина (КаЪ|п) [253]. Кроме того, рандомизированные алгоритмы подробно рассмотрены в учебнике Мотвани (Мопчаш) и Рагтвагана (КайЫтайап) [228].
Различные варианты задачи о найме сотрудника изучались многими исследователями. Этот класс задач более известен как "задачи о секретарях". Примером работы в этой области является статья Айтаи [А]1а1), Меггидо [Ме881до) и Ваартса ['ттаапв) [12]. ЧАС ТЫ1 Сортировка и порядковая статистика Введение В этой части представлено несколько алгоритмов, с помощью которых можно решить следующую задачу сортировки.
Вход: последовательность, состоящая из п чисел (аы аз,..., а„). Выход: перестановка (изменение порядка) (а',а',...,а'„) входной последовательности таким образом, что а', < аз « . а'„. Входная последовательность обычно представляется в виде и-элементного массива, хотя она может иметь и другое представление, например, в виде связанного списка. Структура данных На практике сортируемые числа редко являются изолированными значениями. Обычно каждое из них входит в состав набора данных, который называется заиисью (гесоп1). В каждой записи содержится ключ (лисеу), представляющий собой сортируемое значение, в то время как остальная часть записи нередко состоит из сопутствующих данных, дополняющих ключ.
Алгоритм сортировки на практике должен быть реализован так, чтобы он вместе с ключами переставлял и сопутствующие данные. Если каждая запись включает в себя сопутствующие данные большого объема, то с целью свести к минимуму перемещение данных сортировка часто производится не в исходном массиве, а в массиве указателей на записи. В определенном смысле сделанное выше замечание относится к особенностям реализации, отличающим алгоритм от конечной программы.
Метод, с помощью которого процедура сортировки размещает сортируемые величины в нужном порядке, не зависит от того, сортируются ли отдельные числа или большие записи. Таким образом, если речь идет о задаче сортировки, обычно предполагается, что входные данные состоят только из чисел. Преобразование алгоритма, предназначенного для сортировки чисел, в программу для сортировки записей не представляет концептуальных трудностей, хотя в конкретной практической ситуации иногда возникают различные тонкие нюансы, усложняющие задачу программиста.
Почему сортировка? Многие исследователи, работающие в области вычислительной техники, считают сортировку наиболее фундаментальной задачей при изучении алгоритмов. Тому есть несколько причин. ° Иногда в приложении не обойтись без сортировки информации. Например, чтобы подготовить отчет о состоянии счетов клиентов, банку необходимо выполнить сортировку чеков по их номерам. Часть 11.
Сортировка и порядковая статистика 175 ° Часто в алгоритмах сортировка используется в качестве основной подпрограммы. Например, программе, выполняющей визуализацию перекрывающихся графических объектов, которые находятся на разных уровнях, сначала может понадобиться отсортировать эти обьекты по уровням снизу вверх, чтобы установить порядок их вывода. В этой книге мы ознакомимся с многочисленными алгоритмами, в которых сортировка используется в качестве подпрограммы. ° Имеется большой выбор алгоритмов сортировки, в которых применяются самые разные технологии. Фактически в алгоритмах сортировки используются многие важные методы (зачастую разработанные еще на заре компьютерное эры), применяемые при разработке различных классов алгоритмов.
В этом отношении задача сортировки представляет также исторический интерес. ° Сортировка — это задача, для которой можно доказать наличие нетривиальной нижней границы (что будет сделано в главе 8). Найденные верхние границы в асимптотическом пределе совпадают с нижней границей, откуда можно заключить, что наши алгоритмы сортировки являются асимптотнчески оптимальными. Кроме того, нижние оценки алгоритмов сортировки можно использовать для поиска нижних границ в некоторых других задачах. ° В процессе реализации алгоритмов сортировки на передний план выходят многие прикладные проблемы. Выбор наиболее производительной программы сортировки в той или иной ситуации может зависеть от многих факторов„таких как предварительные знания о ключах и сопутствующих данных, об иерархической организации памяти компьютера (наличии нэша и виртуальной памяти) и программной среды. Многие из этих вопросов можно рассматривать на уровне алгоритмов, а не кода.
Алгоритмы сортировки В главе 2 читатель имел возможность ознакомиться с двумя алгоритмами, производящих сортировку п действительных чисел. Сортировка методом вставок в наихудшем случае выполняется за время ~Э (пз). Несмотря на далеко не самое оптимальное асимптотическое поведение этого алгоритма, благодаря компактности его внутренних циклов он быстро справляется с сортировкой массивов с небольшим количеством элементов "на месте" (без дополнительной памяти, т.е.
без выделения отдельного массива для работы и хранения выходных данных). (Напомним, что сортировка выполняется без дополнительной памяти лишь тогда, когда алгоритму требуется только определенное постоянное количество элементов вне исходного массива.) Сортировка методом слияния в асимптотическом пределе ведет себя как 9(п 18п), что лучше, чем О (пз), но процедура МпксЕ, которая используется в этом алгоритме, не работает без дополнительной памяти. 17б Часть П. Сортировка и порядковая статистика В этой части вы ознакомитесь еще с двумя алгоритмами, предназначенными для сортировки произвольных действительных чисел. Представленный в главе 6 метод пирамидальной сортировки позволяет отсортировать и чисел за время 0(п18 и).
В нем используется важная структура данных, пирамида, или куча (Ьеар), которая также позволяет реализовать приоритетную очередь. Рассмотренный в главе 7 алгоритм быстрой сортировки также сортирует и чисел "на месте", но время его работы в наихудшем случае равно 9 (пз). Тем не менее, в среднем этот алгоритм выполняется за время О (п 18 и) и на практике по производительности превосходит алгоритм пирамидальной сортировки. Код алгоритма быстрой сортировки такой же компактный, как и код алгоритма сортировки вставкой, поэтому скрытый постоянный множитель, влияющий на величину времени работы этого алгоритма, довольно мал. Алгоритм быстрой сортировки приобрел широкую популярность для сортировки больших массивов.
Алгоритмы сортировки, работающие по методу вставок и слияния, а также алгоритмы пирамидальной и быстрой сортировки имеют одну общую особенность — все они работают по принципу попарного сравнения элементов входного массива. В начале главы 8 рассматривается модель дерева принятия решения, позволяющая исследовать ограничения производительности, присущие алгоритмам данного типа. С помощью этой модели доказывается, что в наихудшем случае нижняя оценка, ограничивающая время работы любого алгоритма, работающего по методу сравнения, равна Й (и 18 п).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
