1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 23
Текст из файла (страница 23)
3. СОРТИРОВКА И ПОРЯДКОВЫЕ СТАТИСТИКИ 1=7, и все время в А[)],..., А[« — 11 будут находиться элементы нз 5,. Аналогично вначале)=1, а в А[)+11, ..., А[1) все время будут находиться элементы из 5,[) 5,. Это разбиение производит подпрограмма на рис. 3.8. Затем можно вызвать БЫСТРСОРТ для массива А[71, ..., А[« — 11, т. е. 5„и для массива А [)+11, ..., А[11, т. е. 5, [«5,. Но если «=7' (н тогда 5,=йу), то надо сначала удалить из 5, [) 5, хотя бы один элемент, равный а.
Удобно удалять тот элемент, по которому производилось разбиение. Следует также заметить, что если это представление в виде массива применяется для последовательностей, то можно подать аргументы для БЫСТРСОРТ, просто поставив указатели на первую и последнюю ячейку используемого куска массива. Пример 3.6. Разобьем массив А 1 2 3 а 5 8 7 8 9 по элементу а=3, «РЬПе-оператор (строка 4) уменьшает ) с 9 до 7, поскольку числа А[91=3 и А181=8 оба не меньше а, но А[71=1(а. Строка 6 не увеличивает 1 с его начального значения 1, поскольку А[11=6)~. Поэтому мы переставляем А[11 и А[7), полагаем «=2, 1=6 н получаем массив на рис.
3.9, а. Результаты, получаемые после следующих двух срабатываний цикла в строках 3 — 9, показаны на рис. 3.9, б и в. В этот момент «)), и выполнение вЬ«[е-оператора, стоящего в строке 3, заканчивается. П ,/ Рнс. 3.9. Разбиение массива. 116 З.я. ПОРЯДКОВЫЕ СТАТИСТИКИ 3.6. ПОРЯДКОВЫЕ СТАТИСТИКИ С упорядочением тесно связана задача нахождения й-го наименьшего элемента в л-элементной последовательности '). Одно из очевидных решений состоит в следующем: упорядочить эту последовательность в порядке неубывания ее элементов и взять й-й элемент. Как мы уже видели, это потребует и 1оя и сравнений. Аккуратно применяя стратегию "разделяй и властвуй", можно найти й-й наименьший элемент за 0(л) шагов.
Важный частный случай — й= = Г и/2 ); в этом случае середина последовательности отыскивается за линейное время. Алгоритм 3.6. Нахождение Ф-го наименьшего элемента Вход. Последовательность 5 из и элементов, принадлежащих линейно упорядоченному множеству, и целое число й, 1(ймп. Выход. й-й наименьший элемент последовательности 5. Метод. Применяется рекурсивная процедура ВЫБОР, приве. денная на рис. 3.!О. 0 Проанализируем алгоритм 3.6 на интуитивном уровне, чтобы увидеть, почему он работает, как надо. Основная идея — данная последовательность разбивается по некоторому элементу и иа такие три подпоследовательности 5„ 5„ 5„ что 5, содержит все элементы, меньшие т, 5, — все элементы, равные гп, и 5, — все элементы, большие лт.
Сосчитав число элементов в 5, и 5„ можно узнать, в каком из множеств 5„5, и 5, лежит Й-й наименьший элемент. Таким приемом можно свести данную задачу к меньшей. Чтобы получить линейный алгоритм, надо уметь за линейное время находить разбивающий элемент так, чтобы длина каждой из подпоследовательностей 5, и 5, была бы не больше фиксированной доли длины последовательности 5. Вся хитрость в способе выбора разбивающего элемента т.
Последовательность 5 разбивается на подпоследовательности по пять элементов в каждой. Каждая подпоследовательность упорядочивается, и из медиан всех этих подпоследовательностей составляется последовательность М. Теперь М содержит только ~ и/6 1 элементов, и можно найти ее медиану в пять раз быстрее, чем у последовательности из п элементов.
Далее, не меньше четверти всех элементов последовательности 5 не превосходят и, и не меньше четверти ее элементов больше или равны гл. Это проиллюстрировано на рис. 3.11. Возникает вопрос: причем здесь "магическое число*' 6? Ответ заключается в том, что процедура ВЫБОР рекурсивно вызывается два раза, каждый раз '1 Строго говоря, й-м наименыаим элементом последовзтельностн ам аэ,... ..., а„нвзмвяется такой элемент Ь этой последовательности, что а;<Ь не более чем для й — 1 значений! н аг~Ь не менее чем для й знзченнй Ь Например, 4 — второй н третий наименьший элемент последовательности 7, 4, 2, 4. 117 гл.
в. соитииовкл и поиядковыи статистики ргосег(пге ВЫБОР(Ь, 5); 1. 1! ) 5 ) ( 50 ййеп Ьей(п 2. упорядочить 5; 3. ге1пгп Ь-й наименьший элемент в 5 епб е1зе Ьей(п 4. разбить 5 на ~!5)!6 ) последовательностей по 6 элементов в каждой; 6. при этом останется не более четырех неиспользованных элементов; 6. упорядочить каждую пятиэлементную последовательность; 7.
пусть М вЂ” последовательность медиан этих пятиэлементных множеств; 8. от — ВЫБОР(~ )М!(2 ), М); 9. пусть 5„5, и 5,— последовательности элементов из 5, соответственно меньших, равных и больших т; 10. 1! !5г()Ь 1Ьеп ге!игп ВЫБОР(Ь, 5,) е1зе (т () 5,)+(5е1 э Ь) !Ьеп ге1пгп т е!зе ге!игп ВЫБОР(Ь вЂ” 15,) — 15,), 5 ) епд !1 12 Рис. 3.10. Алгоритм выбора А-го наименьшего анемента.
Теорема 3.9. Алгоритм 3.6 находит Ь-й наименьший элемент в и-элементной ооследоваотельности 5 за время 0(о). Л о к а з а т е л ь и т в о. Корректность алгоритма доказывается непосредственно индукцией по )5!, и эту часть доказательства мы оставляем в качестве упражнения. Пусть Т(а) — время, затра- ттв на последовательности, длина которой равна некоторой части длины последовательности 5. Чтобы алгоритм работал линейное время, сумма длин этих двух последовательностей должна быть меньше |5|.
Числа, отличные от 6, также годятся, но для некоторых из них процесс упорядочения подпоследовательностей будет дольше. В качестве упражнения предлагаем выяснить, какие же числа можно использовать вместо 6. з.т. сРЕдНЕЕ ВРемя для пОРЯДкОВЫх сТАтистик ЭЛемЕнты, меньане иет равтт т 1 ° ° ° ° 1 (.лlз.) уаорядоненны» лослИгиеятлыььс м", яре дстаоленеыи е виде сто»дион с наименьы Ллементом наверну ° ° ° Лоследоеттелигссни Ф иеобралгенна» е уояо»- сЪенном виде ° 1 ° ° ° ° 1 1 1 ° 1 ° ° ° ° 1 э ° ° Элементы, до»мане или роение т Рис.
3.11. Разбиение 3 по алгоритму 3.6. Из (3.8) по индукции можно доказать, что Т(п)(20 сп. (З 3.7. СРЕДНЕЕ ВРЕМЯ ДЛЯ ПОРЯДКОВЫХ СТАТИСТИК В этом разделе мы изучим среднее время, затрачиваемое на выбор й-го наименьшего элемента в последовательности из и элементов. ьг(ы увидим, что для нахождения й-го наименьшего элемента требуется провести по меньшей мере а — ! сравнений как в худшем случае, так и в среднем. Поэтому выбирающий алгоритм, описанный в предыдущем разделе, с точностью до постоянного множителя оптимален в классе деревьев решений.
Здесь мы приведем другой выбирающий алгоритм, который имеет квадратичную сложность в худшем случае, чиваемое на выбор й-го наименьшего элемента из последовательности длины и. Длина последовательности М, составленной из медиан подпоследовательностей, не болыпе п!5, и потому рекурсивный вызов процедуры ВЫБОР(~ 1М1/2 ~, М) занимает время, не большее Т (пlб). Каждая из последовательностей 5, и 5, имеет длину не более Зпг4.
Чтобы увидеть это, заметим, что не менее ~ п/1О ~ элементов последовательности М больше или равны га и для каждого из них найдутся в 5 два различных элемента, которые так же соотносятся с аг. Следовательно, 15г ~(п — 3 ~ пПО ~, т. е. при и В50 длина последовательности 5, меньше Зп/4, Аналогичное рассуждение применимо и к 5,. Поэтому рекурсивный вызов в строке 10 или 12 занимает времени не более Т(Зла). Все остальные операторы тратят не более 0(п) времени. Таким образом, для некоторой постоянной и сп для п(49, Т (и)( Т(п/5)+Т(Зп(4)+сп для и) 50.
гл. з. соптипоикя и попядкоиыи статистики ио среднее время работы которого составляет лишь долю времени работы алгоритма 3.6. Пусть 5= (а„ а„ ..., а„) — множество из и различных элементов, а Т вЂ” дерево решений какого-иибудь алгоритма для иахождения й-го наименьшего элемента в 5. Каждый путь р в Т определяет такое отношение зс иа 5, что а,херам если два различных элемеита а; и аз сравниваются в некотором узле, лежащем иа р, и в результате этого сравнения либо а,(ан либо а; а; ').
Пусть Я;, — траизитивиое замыкание отношения зсрз). Образно говоря, если а, Я' ан то последовательность сравнений, представленная путем р, выясняет, что аз(ан поскольку никакой элемеит ие сравиивается сам с собой. Лемма З.З. Если на пути р выясняетсл, что а является А-м наименьшим элементом в 5, то для любсео зчьт, 1(зя-.п, либо а;Яр~аео либо а Я,",ан Д о к а з а тел ь от в о. Допустим, что некоторый элемент а ие связан с а отношением Рр. Покажем, что, поместив а, либо перед, либо после а„в линейном порядке, заданном иа 5, мы получим противоречие с предположением, что путь р правильно установил, что а„является й-и наименьшим элементом в 5.
Пусть 5,= =(а;~аэзс+а,), 5,=(ау(а„Я+ау) и в 5, входят остальные элемеиты из 5. По предположению а, и а принадлежат 5,. Если ау — произвольный элемент в 5, (соответствеиио в Я,) и а, Яр' ау (соответствеиио а; Я+раз), то в силу траизитивиости а, также прйиадлежит 5, (соответствеиио 5,). Следовательно, можно построить такой линейный порядок )с, совместимый с Я+, что все элементы множества 5, предшествуют всем элементам из 5„кс торые в свою очередь предшествуют всем элементам из 5,. По предположению элемент а, ие связан отношением Р+а ии с одним элементом из 5,. Допустим, что а, предшествует а„прй лииейиом порядке Р, т. е. а, зс а„.
Тогда можно построить новый линейный порядок Г, совпадающий с )с во всем, кроме того, что а„ следует непосредственно за а . Отношение Я' также совместимо с Я . Для каждого порядка ьс и Я' можно найти различные элемеиты, удовлетворяющие соответственно Я или Я'. Но а ие может быть й-м наименьшим элементом в обоих случаях, так как в Я' элемеиту а предшествует иа один элемент меньше, чем в Я. Г[оэтому заключаем, что если какой-то элемент из 5 ие связан с а ') Напомним, что мы предполагаем, что каждое срааиеиие и с Ь дает результат о(Ь или Ь~а. В случае ог(о срааиииался элемент о; с о~., и случае а;~ау срааииаался элемент ау с ао з) Тронаитиеным замыканием отношения й называется такое отношение что сЯ " Е тогда и только тогда, когда сушестаует последовательность истинных утверждений аида е, й ез, ез й е„..., е„, зйеи, где ш)2, с=ее и в=е .
130 КТ. сРеднее ВРемя для поРядкоВ|их стАтистик отношением НР, то дерево Т не может правильно выбрать й-й наименьший элемент из 5. Случай а„йа„исследуется аналогично. С! Теорема 3.10. Если Т вЂ” дерево решений, выбирающее я-й наименьший элемент в множестве 5, 3Щ =и, то глубина любого листа дерева Т не меньше а — 1. Доказательство.
Рассмотрим путь р в Т из корня к листу. По лемме 3.3 либо а, )тр а„, либо а„йэ а| для каждого еоьт, где а„— элемент, выбраннйй в качестве й-го наименьшего. Для элемента аь !чьт, определим ключевое сравнение как первое сравнение на р, содержащее а, и такое, что выполнено одно из условий: 1) а| сравнивается с аРР 2) а| сравнивается с ад а| Крат и ат Яра„, 3) а, сравнивается с ад а; )тр а, и а„й+Р аь Интуитивно ключевое сравнение для а; — это первое сравнение, нз которого можно определить, предшествует элемент а, элементу а или следует за ним.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
