Алгоритмы - построение и анализ (1021735), страница 41
Текст из файла (страница 41)
Сопоставляя уравнения (7.2) и (7.3), получаем: Е[Х] = ,'1 1=1 уии+1 Эту сумму можно оценить, воспользовавшись заменой переменных (Й = 1 — 1) и границей для гармонического ряда (уравнение (А.7)): 2 з з 2 и — 1 и-1 < и-1 = ,'1 0(1кп) = 0(п1яп). и-1 и Е[Х] = ,'1 1=1 3=1+1 (7.4) Таким образом, можно сделать вывод, что при использовании процедуры Клы00м!ве0 РАкт1т101ч математическое ожидание времени работы алгоритма быстрой сортировки различающихся по величине элементов равно 0 (п 1к п).
Упражнения 7.4-1. Покажите, что в рекуррентном соотношении Т(п) = 1пах (Т(д) + Т(п — д — 1)) + 9(п), с<я<и-1 Т(п) = й (п ) . Теперь вычислим вероятность этого события. Перед тем как в множестве Уц будет выбран опорный элемент, все это множество является не разделенным, и любой его элемент с одинаковой вероятностью может стать опорным.
Поскольку всего в этом множестве 1 — г + 1 элемент, а опорные элементы выбираются случайным образом и независимо друг от друга, вероятность того, что какой- либо фиксированный элемент первым будет выбран в качестве опорного, равна 1Я вЂ” г + 1). Таким образом, выполняется следующее соотношение: Часть !!. Сортировка и порядковая статистика 214 7.4-2.
Покажите, что в самом благоприятном случае время работы алгоритма быстрой сортировки равно П 1н !я и). 7.4-3. Покажите, что функция»?з+(и — »7 — 1) на множестве»! = О, 1,...,п — 1 достигает максимума при»7 = О или д = п — 1. 7.4-4. Покажите, что математическое ожидание времени работы процедуры КАноом1гео ЯО1скзонт равно П 1н1ки). 7.4-5.
На практике время работы алгоритма быстрой сортировки можно улучшить, воспользовавшись тем, что алгоритм сортировки по методу вставок быстро работает для "почти" отсортированных входных последовательностей. Для этого можно поступить следующим образом. Когда процедура быстрой сортировки начнет рекурсивно вызываться для обработки подмассивов, содержащих менее й элементов, в ней не будет производиться никаких действий, кроме выхода из процедуры.
После возврата нз процедуры быстрой сортировки, вызванной на самом высоком уровне, запускается алгоритм сортировки по методу вставок, на вход которого подается весь обрабатываемый массив. На этом процесс сортировки завершается. Докажите, что математическое ожидание времени работы такого алгоритма сортировки равно О 1тй + и 1б (и/1с) ). Как следует выбирать значение 1с, исходя из теоретических и практических соображений? * 7.4-6. Рассмотрим модификацию процедуры РАнт1т1он путем случайного выбора трех элементов массива А и разбиения массива по медиане выбранных элементов (т.е.
по среднему из этих трех элементов). Найдите приближенную величину вероятности того, что в худшем случае разбиение будет произведено в отношении а к 11 — »з), как функцию от а в диапазоне О < »з < 1. Задачи 7-1. Корректность разбиения по Хоару Представленная в этой главе версия процедуры РАкт1т1он не является реализацией первоначально предложенного алгоритма. Ниже приведен исходный алгоритм разбиения, разработанный Хоаром (С.А.К.
Ноаге): НоАкн РАнт!т1ом1А, р, г) 1 я -А[р) 2 㻠— р — 1 3 з -г+1 4 н 'и!!е ткал 5 бо гереаг з + — 7' — 1 Глава 7. Быстрая сортировка 218 нп61 А[1] < х гереаФ 1 — 1+ 1 пп61 А[1] > х !11< 7 Феп Обменять А[а] + А[з] е1ве ге1игп 7' б 7 8 9 10 11 а) Продемонстрируйте, как работает процедура Нолкн Рлкт~тюн с входным массивом А = (13,19,9,5,12,8,7,4, П,2,6,21). Для этого укажите, чему будут равны значения элементов массива и значения вспомогательных переменных после каждой итерации цикла ий11е в строках 4 — 11. В следующих трех заданиях предлагается привести аргументы в пользу корректности процедуры Нолкн Рлкт~тюн.
Докажите следующие утвер- ждения. б) Индексы г и 7' принимают такие значения, что обращение к элементам массива А, находящимся за пределами подмассива А [р..т], никогда не произойдет. в) По завершении процедуры Нолкв Рлкт~т1он возвращается значение 1, такое что р < 7' < т. г) По завершении процедуры Нолкн Рлкт~тюн каждый элемент подмассива А [р..Я не превышает значений каждого элемента подмассива А [7'+ 1..т]. В описанной в разделе 7.1 процедуре Рлкт171он опорный элемент (которым изначально является элемент А [т]) отделяется от двух образованных с его помощью подмассивов.
В процедуре же Нолке Рлкт~т10н, напротив, опорный элемент (которым изначально является элемент А [р]) всегда помещается в один из двух полученных подмассивов: А [р..7] илн А [7' + 1..т]. Поскольку р < 7' < т, это разбиение всегда нетривиально. д) Перепишите процедуру Яоюкзокт таким образом, чтобы в ней использовалась процедура Нолке Рлкт1т10х. 7-2. Альтернативный анализ быстрой сортировки Можно предложить альтернативный анализ рандомнзнрованной быстрой сортировки, в ходе которого внимание сосредотачивается на математическом ожидании времени, которое требуется для выполнения каждого рекурсивного вызова процедуры Яи!скзокт, а не на количестве производимых сравнений. Часть П.
Сортировка и порядковая статистика 216 а) Докажите, что вероятность того, что какой-либо заданный элемент и-элементного массива будет выбран в качестве опорного, равна 1/и. Опираясь на этот факт, определите индикаторную случайную величину Х; = 1(1-й в порядке возрастания элемент выбран опорным) . Какой смысл имеет величина Е [Х;]? б) Пусть Т(п) — случайная величина, обозначающая время работы алгоритма быстрой сортировки и-элементного массива. Докажите, что Е[Т(и)] = Е ~~) Хд(Т(д — 1) + Т (и — д) + О (и)) д=з (7.5) в) Покажите, что уравнение (7.5) можно представить в виде 2 и-1 Е [Т (и)) = — ~ Е [Т (д)) + О (и) .
4=2 (7.6) г) Покажите, что 3 1 2 ~~> Й18Й < — и 18и — — и . 2 8 (7.7) (Указание: разбейте сумму на две части, в одной из которых суммированиепроводитсяпоиндекса)с = 2,3,..., )п(2[ — 1,авдругой— по индексам /с = [и/2],..., и — 1.) д) Покажите с помощью неравенства (7.7), что решение рекуррентного соотношения (7.6) имеет вид Е [Т(п)) = 9 (и 18 п). (Указание: с помощью подстановки покажите, что Е [Т(п)] < оп 18п для достаточно больших п и некоторой положительной константы а.) 7-3. Блуждающая сортировка Два профессора предложили "элегантный" алгоритм сортировки, который выглядит следующим образом: 8тооан 8окт(А, г,у) 1 Ы А[1) > А[7] 2 сйеп Обменять А[а] А[7] 3 11' г+ 1 > 7' 4 слеп гегпгп 5 )с ~ — [(7' — 1+ 1)/3] с Округление в меньшую сторону 6 8тооон 8онт(А, г,у' — )с) ь Первые две трети 7 8тооон 8окт(А,1+ )с,7') с> Последние две трети 8 8тооон 8окт(А, г,у — lс) с> Снова первые две трети Глава 7.
Быстрая сортировка 217 а) Докажите, что если и = 1епдй [А], то процедура Зтооон бокт(А,1, 1епдгй [А]) корректно сортирует входной массив А [1..п]. б) Запишите рекуррентное соотношение для времени работы процедуры Зтооое Зокт и дайте точную асимптотическую границу (в О- обозначениях) этой величины. в) Сравните время работы процедуры Зтооон Зонт в наихудшем случае со временем сортировки вставкой, сортировки слиянием, пирамидальной сортировки и быстрой сортировки. Достойны ли эти профессора своих званий? 7-4. Глубина стека дли быстрой сортировки В описанном в разделе 7.1 алгоритме Оглскзокт содержатся два рекурсивных вызова этого же алгоритма.
После вызова процедуры Рлкптюн полученные в результате правый и левый подмассивы рекурсивно сортируются. Второй рекурсивный вызов процедуры Яо1скзокт на самом деле не является необходимым; его можно избежать с помощью итеративной управляющей структуры. Этот метод, получивший название оконечной рекурсии (1а(! геспгз1оп), автоматически обеспечивается хорошими компиляторами.
Рассмотрите приведенную ниже версию быстрой сортировки, в которой имитируется оконечная рекурсия: Яглскзокт'(А,р,г) 1 зтййер(т 2 бо ~> Разбиение и сортировка левого подмассива 3 д — Рлкт~т1ом(А, р, г) 4 Оо1скзокт'(А, р, д — 1) 5 р< — я+ 1 а) Докажите, что процедура Оо1скзокт'(А,1, 1епдЮ [А]) корректно сортирует входной массив А. Обычно компиляторы выполняют рекурсивные процедуры с помощью стека, содержащего необходимую информацию, в том числе и значения параметров, применяющихся для каждого рекурсивного вызова.
Информация о самом последнем вызове находится на верху стека, а информация о начальном вызове — на его дне. При вызове процедуры информация записывается в стек (роялей), а при ее завершении — выталкивается (рорреб) из него. Поскольку предполагается, что массивы-параметры представлены указателями, при каждом обращении процедуры к стеку передается информация объемом О (1). Глубина стека (з1аск бербз)— это максимальная величина стекового пространства, которая используется в ходе вычисления.
Часть 11. Сортировка и порядковая статистика 218 6) Опишите сценарий, в котором глубина стека, необходимая для обработки процедурой Оглскзокт' п-элементного массива, равна 9 (и). в) Модифицируйте код процедуры Оглскзокт' так, чтобы необходимая для ее работы глубина стека в наихудшем случае была равна О (1йп). Математическое ожидание времени работы алгоритма О (п 18 и) должно при этом остаться неизменным. 7-5. Разбиение по медиане трех элементов Один из способов улучшения процедуры КАмоом~хвоЯглскзокт заключается в том, чтобы производить разбиение по опорному элементу, определенному аккуратнее, чем путем случайного выбора.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
