Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 51
Текст из файла (страница 51)
Сортировка столбцами из задачи 8.7 разработана Лейтоном (Ье(8Ыоп) [226]. Глава 9. Медианы и порядковые статистики Будем называты-й порядковой статисгникой (огбег зГайайс) множества, состоящего из и элементов, (-й элемент в порядке возрастания. Например, минимум такого множества — это первая порядковая статистика (( = 1), а его максимум— зто и-я порядковая статистика (! = и). Медиана (шегйап) неформально обозначает середину множества. Если и нечетное, то медиана единственная, и ее индекс равен ! = (и + 1)/2; если же п четное, то медианы две, и их индексы равны ( = и/2 и г = и/2+ 1. Таким образом, независимо от четности п, медианы располагаются при ( = '((и + 1)/2) (нижняя медиана (1ожег шегйап)) и 1 = ~(п + 1) /21 (верхняя медиана (пррег шегйап)).
Однако для простоты в этой книге термин "медиана" относится к нижней медиане. Данная глава посвящена задаче выбора (-й порядковой статистики в множестве, состоящем из п различных чисел. Для удобства предположим, что все числа множества различны, хотя почти все, что мы будем делать, обобщается на случай, когда некоторые значения в множестве повторяются. Формально задачу выбора (зе(есбоп ргоЫеш) можно определить следующим образом. Вход. Множество А, состоящее из и (различных) чисел, и число 1 < ( < и. Выход.
Элемент х Е А, превышающий по величине ровно 1 — 1 других элементов множества А. Задачу выбора можно решить за время О(п !я и). Для этого достаточно выполнить сортировку элементов с помощью пирамидальной сортировки или сортировки слиянием, а затем просто извлечь элемент выходного массива с индексом (. Однако в этой главе представлены более быстрые алгоритмы. В разделе 9.! рассматривается задача о выборе минимального и максимального элементов множества. Больший интерес представляет общая задача выбора, которая исследуется в двух последующих разделах.
В разделе 9.2 анализируется применяющийся на практике рандомизированный алгоритм, ожидаемое время работы которого составляет 0(п) в предположении, что все элементы различны. В разделе 9.3 приведен алгоритм, представляющий более теоретический интерес, время работы которого достигает величины 0(п) в наихудшем случае. Части И. Сортировка и яорядковая статистика 9.1. Минимум и максимум Сколько сравнений необходимо для того, чтобы найти минимальный элемент в и-элементном множестве? Для этой величины легко найти верхнюю границу, равную п — 1 сравнениям: мы по очереди проверяем каждый элемент множества и следим за тем, какой из них является минимальным на данный момент.
В представленной ниже процедуре предполагается, что исследуется множество, состоящее из элементов массива А, где А, !епд!й = и. М!и!мам!А) ! т!и = А[1) 2 !ог ! = 2 со А. 1епд!Ь 3 !Г т!и ) А[!) 4 тт = А[!] 5 ге!ага т!и Очевидно, что для поиска максимального элемента также понадобится не более п — 1 сравнений. Является ли представленный выше алгоритм оптимальным? Да, поскольку можно доказать, что нижняя граница для задачи определения минимума также равна и — 1 сравнений. Любой алгоритм, предназначенный для определения минимального элемента множества, можно представить в виде турнира, в котором принимают участие все элементы. Каждое сравнение — это поединок между двумя элементами, в котором побеждает элемент с меньшей величиной.
Важное наблюдение заключается в том, что каждый элемент, кроме победителя, должен потерпеть поражение хотя бы в одном поединке. Таким образом, для определения минимума понадобится п — 1 сравнений, и алгоритм Мич1мцм является оптимальным по отношению к количеству производимых в нем сравнений. Одновременный поиск минимума и максимума В некоторых приложениях возникает необходимость найти как минимальный, так и максимальный элементы множества. Например, графической программе может понадобиться выполнить масштабирование множества координат (х, у) таким образом, чтобы они совпали по размеру с прямоугольной областью экрана или другого устройства вывода. Для этого сначала нужно определить максимальное и минимальное значения координат. Совершенно очевидно, как найти минимум и максимум в и-элементном множестве, производя при этом В(п) сравнений;при этом алгоритм будет асимптотически оптимальным.
Достаточно просто выполнить независимый поиск минимального и максимального элементов. Для выполнения каждой подзадачи понадобится и — 1 сравнений, что в сумме составит 2п — 2 сравнений. Однако на самом деле для одновременного определения минимума и максимума достаточно не более 3 [п/2) сравнений. Для этого необходимо следить за тем, какой из проверенных на данный момент элементов минимальный, а какой— 245 Гла м 9. МгДианн и корядконые статистики максимальный.
Вместо того чтобы отдельно сравнивать каждый входной элемент с текущим минимумом и максимумом (для чего пришлось бы на каждый элемент израсходовать по два сравнения), мы будем обрабатывать пары элементов. Образовав пару входных элементов, сначала сравним их один с другим, а затем меньший элемент пары будем сравнивать с текущим минимумом, а больший— с текущим максимумом. Таким образом, для каждой пары элементов понадобится по три сравнения.
Способ начального выбора текущего минимума и максимума зависит от четности количества элементов в множестве п. Если и нечетно, мы выбираем из множества один из элементов и считаем его значение одновременно и минимумом, и максимумом; остальные элементы обрабатываем парами. Если же п четно, то выбираем два первых элемента и путем сравнения определяем, значение какого из них будет минимумом, а какого — максимумом. Остальные элементы обрабатываем парами, как и в предыдущем случае.
Проанализируем, чему равно полное число сравнений. Если п иечетно, то нужно будет выполнить 3 (п/2)' сравнений. Если же п четно, то выполняется одно начальное сравнение, а затем — еще 3(п — 2)/2 сравнений, что в сумме дает общее количество сравнений, равное Зп/2 — 2. Таким образом, в обоих случаях полное количество сравнений не превышает 3 (и/25. Упражнения 9.1.1 Покажите, что для поиска второго в порядке возрастания элемента в наихудшем случае достаточно п + (оп~ — 2 сравнений.
(Указаниез найдите заодно и наименьший элемент.) 9.1.2 * Докажите, что в наихудшем случае для поиска максимального и минимального среди и чисел необходимо выполнить (Зп/2( — 2 сравнений. (Указакиез рассмотрите вопрос о том, сколько чисел являются потенциальными кандидатами на роль максимума или минимума, и определите, как на это количество влияет каждое сравнение.) 9.2. Выбор в течение линейного ожидаемого времени Общая задача выбора оказывается более сложной, чем простая задача поиска минимума. Однако, как это ни удивительно, время решения обеих задач в асимптотнческом пределе ведет себя одинаково — как О(п).
В данном разделе вниманию читателя представляется алгоритм типа "разделяй и властвуй*' Клппоызснз-Яа.ест, предназначенный для решения задачи выбора. Этот алгоритм разработан по аналогии с алгоритмом быстрой сортировки, который рассматривался в главе 7. Как и в алгоритме быстрой сортировки, в алгоритме Части РЕ Сортировка и порядковая втативтияа КАнпом1хеп-Веьест используется идея рекурсивного разбиения входного массива.
Однако в отличие от алгоритма быстрой сортировки, в котором рекурсивно обрабатываются обе части разбиения, алгоритм КА!чоом1ЕЕО-8ЕЕЕСТ работает лишь с одной частью. Это различие проявляется в результатах анализа обоих алгоритмов; если математическое ожидание времени работы алгоритма быстрой сортировки равно Е!(и 18п), то ожидаемое время работы алгоритма КАноом!еео-Бееест равно Е!(п), в предположении, что все элементы входного множества различны.
В алгоритме КАноом!еео-Беьест используется процедура КАноом!еео- РАкт1Т!Он, впервые представленная в разделе 7.3. Таким образом, подобно процедуре КА1чоом!ееп-Я!!!Скеокт, КАноом!ееп-Веьест — это рандомизированный алгоритм, поскольку его поведение частично определяется выводом генератора случайных чисел. Приведенный ниже код процедуры КА!чоом1ееп-бн.ест возвращает 1-й в порядке возрастания элемент массива А[р .. г). КА!Чоом1ее0-8ееест(А,р,г,1) 1 Ыр==т 2 ге1цгп А[р] 3 д = КАнпом1ееп-РАкт1т1О1ч(А, р, г) 4 В=а — р+1 5 !1 ! == )с // Ответом является опорное значение 6 ге!игп А[9) 7 е1аеЫ1< к 8 ге!цгп КАмоом1еео-Бееест(А,р,д — 1,1) 9 е1ае ге!нгп кА!чоом1еео-Бееест(А, д + 1, г, г' — е) Процедура КА!Ч!ЭОМ!ЕЕП-РАКТ1Т!О!ч работает следующим образом.
В строке 1 выполняется проверка базового случая рекурсии, когда подмассив А[р .. т) состоит из единственного элемента. В этом случае ! должно быть равно 1, и мы просто возвращаем в строке 2 .4[р] как 1-й в порядке возрастания элемент. В противном случае в строке 3 вызывается процедура КА1чпом1гео-РАкт1Т1он, которая разбивает массив А[р .. г! на два (возможно, пустых) подмассива А [р .. д — 1] и А[у+ 1 ..
г], таких, что величина каждого элемента А[р .. д — 1] не превышает значения А[9], которое, в свою очередь, меньше любого из значений элементов А[9 + 1.. г]. Как и в алгоритме быстрой сортировки, элемент А[у) называется опорным (р(го!). В строке 4 процедуры КА!чпом1ееп-бн.ест вычисляется количество элементов й подмассива А[р .. 9], т.е. количество элементов, попадающих в нижнюю часть разбиения плюс один опорный элемент. Затем в строке 5 проверяется, является ли элемент А[9] 1-м в порядке возрастания элементом.
Если это так, то он возвращается в строке 6. В противном случае в алгоритме определяется, в каком из двух подмассивов содержится 1-й в порядке возрастания элемент; в подмассиве А[р .. д — 1] или А[у+1 ., г!. Если ! < lс, то нужный элемент находится в нижней части разбиения, и он рекурсивно выбирается из соответствующего подмассива в строке 8. Если же 1 > Е, то нужный элемент находится в верхней части разбиения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
