Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 105
Текст из файла (страница 105)
Анализ этого случая предлагается выполнить в упражнении 17.4-2. Подведем итог. Поскольку амортизированная стоимость каждой операции ограничена сверху константой, фактическая стоимость выполнения произвольной последовательности из и операций над динамической таблицей равна 0 (и). Упражнения 17.4-1. Предположим, что нужно реализовать динамическую хеш-таблицу с открытой адресацией. Почему может понадобиться считать такую таблицу заполненной, когда ее коэффициент заполнения достигнет некоторого значения а, строго меньшего 1? Кратко опишите, как следует выполнять вставки в динамическую хеш-таблицу с открытой адресацией, чтобы математическое ожидание амортизированной стоимости вставки было равно 0 (1).
Почему математическое ожидание фактичесюй стоимости может быть равным 0 (1) не для всех вставок? !7.4-2. Покажите, что если а; 1 > 1/2 и г-я операция, выполняющаяся над динамической таблицей, — Тли~.е 13и~.нтп, то амортизированная стоимость операции для потенциальной функции (17.6) ограничена сверху юнстантой. 17.4-3. Предположим, что вместо того, чтобы сжимать таблицу, вдвое уменьшая ее размер при уменьшении коэффициента заполнения ниже значения 1/4, мы будем сжимать ее до 2/3 исходного размера, когда значение коэффициента заполнения становится меньше 1/3. С помощью потенциальной функции Ф (Т) = [2 пит [Т[ — вике [Т1[ покажите, что амортизированная стоимость процедуры ТАв~.в Рн.етв, в которой применяется эта стратегия, ограничена сверху константой.
Глава 17. Амортизационный анализ 505 Задачи 17-1. Обратный бинарный битовый счетчик В главе 30 описывается важный алгоритм, получивший название быстрого преобразования Фурье (Раз! Роипег Тгапз1опп, РРТ). На первом этапе алгоритма РРТ выполняется обратная перестановка битов (Ь!1-гечегза! регпппайоп) входного массива А !О..п — Ц, длина которого равна и = 2ь для некоторого неотрицательного целого и. В результате перестановки каждый элемент массива меняется местом с элементом, индекс которого представляет собой преобразованный описанным далее образом индекс исходного элемента.
Каждый индекс а можно представить в виде последовательности й битов (аь ыая з,...,ао), где а = 2„," аз а;2'. Определим операцию гечь ((аь и аь з,..., ао)) = (ао, ап ...,аь 1), т.е. гечь(а) = ~~> аь; 12'. ~=о Например, если и = 16 (или, что эквивалентно, й = 4), то гечь (3) = = 12, поскольку 4-битовое двоичное представление числа 3 выглядит как 0011, и в результате преобразования юторого получим 1!00, те.
4- битовое двоичное представление числа 12. а) Пусть имеется функция гечы выполняющаяся в течение времени 6 (и). Разработайте алгоритм обратной перестановки битов в массиве длиной и = 2", время работы юторого равно О (и!с). Чтобы улучшить время перестановки битов, можно воспользоваться алгоритмом, основанным на амортизационном анализе. Мы поддерживаем счетчик с обратным порядком битов и процедуру В!т Внчнкзеп 1мскемемт, которая для заданного показания счетчика а возвращает значение течь (гечь (а) + 1).
Например, если й = 4 и счетчик начинает отсчет от О, то в результате последовательных вызовов процедуры В!т Кнчнию 1!чскнмичт получим последовательность 0000,1000,0100,1100,0010,1010, . = 0,8,4,12,2,10, б) Предположим, что слова в компьютере хранятся в виде й-битовых значений и что в течение единичного промежугка времени компьютер может произвести над этими бинарными значениями такие операции, как сдвиг влево или вправо на произвольное число позиций, побитовое и, побитовое или и т.п. Опишите реализацию процедуры Часть |Ч. Усовершенствованные методы разработки и анализа 506 Вгг Кнчнкзнп 1нскнмннт, позволяющую выполнять обращение порядка битов и-элементного массива в течение времени О (и).
в) Предположим, что в течение единичного промежутка времени сдвиг слова вправо или влево можно произвести только на один бит. Сохраняется ли при этом возможность реализовать обращение порядка битов в массиве за время О (и)? 17-2. Динамический бинарный поиск Бинарный поиск в отсортированном массиве осуществляется в течение промежутка времени, описываемого логарифмической функцией, однако время вставки нового элемента линейно зависит от размера массива.
Время вставки можно улучшить, используя несколько отсортированных массивов. Предположим, что операции Янлксн и 1нзнкт должны поддерживаться для и-элементного множества. Пусть й = [1я(п+ 1)] и пусть бинарное преставление числа и имеет вид (пя м па я,...,по). У нас имеется й таких отсортированных массивов Ао, А~,..., Аь м что для всех 1 = = О, 1,..., а — 1 длина массива А; равна 2'. Каждый массив либо заполнен, либо пуст, в зависимости от того, равно ли тн = 1 или п; = О соответственно.
Таким образом, полное количество элементов, хранящихся во всех 7я массивах, равно 2 „„п;2' = и. Хотя каждый массив отсортирован, между элементами различных массивов нег никаких отношений. а) Опишите, как в этой структуре данных реализовать операцию Янлксн. Проанализируйте время ее работы в наихудшем случае. б) Опишите, как в эту структуру данных вставлять новый элемент. Проанализируйте время выполнения этой операции в наихудшем случае и ее амортизированное время работы.
в) Обсудите реализацию процедуры РБ.етн. 17-3. Амортизироваиные сбалансированные по весу деревья Рассмотрим обычное бинарное дерево поиска, расширенное за счет добавления к каждому узлу х поля вяае [х], содержащего количество ключей, которые хранятся в поддереве с корнем в узле х. Пусть а — константа из диапазона 1/2 < а < 1. Назовем данный узел х асбалансироваиамм (а-Ьа!апосля), если яяе [1е71 [х]] < а . я(яе [х] и въяве [ттдМ [хЦ < а я(яе [х] . Дерево в целом является а-сбалансированным (ст-Ьа1апсед), если о-сбалансирован каждый его узел. Описанный ниже амортизированный подход к сбалансированным деревьям был предложен Варгисом (О. ЧагяЬеяе).
Глава 17. Амортизационный анализ 507 а) В определенном смысле 1/2-сбалансированное дерево является наиболее сбалансированным. Пусть в произвольном бинарном дереве поиска задан узел х. Покажите, как перестроить поддерево с корнем в узле х таким образом, чтобы оно стало 1/2-сбалансированным. Время работы алгоритма должно быть равным 9 (ззке [х]), а обьем используемой вспомогательной памяти — О (зкае [х]). б) Покажите, что поиск в бинарном а-сбалансированном дереве поиска с п узлами в наихудшем случае выполняется в течение времени О (1кп).
При выполнении оставшейся части этой задачи предполагается, что константа а строго больше 1/2. Предположим, что операции 1нзект и Рееете реализованы так же, как и в обычном бинарном дереве поиска с п узламн, за исключением того, что после каждой такой операции„если хоть один узел дерева не является а-сбалансированным, то поддерево с самым высоким несбалансированным узлом "перестраивается" так, чтобы оно стало 1/2-сбалансированным. Проанализируем эту схему с помощью метода потенциалов. Для узла х, принадлежащего бинарному дереву поиска Т, определим величину Ь (х) = [а1зе [1е/Г [х]] — зие [пдй8 [х]] [, а потенциал дерева Т определим как Ф(Т) =с ) Ьх, хет:п(х)>2 где с — достаточно большая константа, зависящая от а. в) Покажите, что потенциал любого бинарного дерева поиска всегда неотрицателен и что потенциал 1/2-сбалансированного дерева равен О.
г) Предположим, что гп единиц потенциала достаточно для оплаты перестройки поддерева, содержащего т узлов. Насколько большой должна быль константа с для данного а, чтобы амортизированное время перестройки полдерева, не являющегося о-сбалансированным, было равным 0 (1)? д) Покажите, что амортизированное время вставки узла в а-сбалансированное дерево с и узлами, как и удаления узла из зтого дерева„ равно О (1я и).
508 Часть !Ч. Усовершенствованные методы разработки н анализа 17-4. Стоимость перестройки красно-черных деревьев Имеется четыре основных операции над красно-черными деревьями, которые выполняют согрукшурные модификации (зцпспца! шоййса6опз): вставка узла, удаление узла, поворот и изменение цвета.
Мы убедимся, что для поддержки свойств красно-черных деревьев в процедурах КВ 1нзект и КВ Редеете достаточно использовать О (1) операций поворота, вставки узлов и удаления узлов, но в них потребуется намного больше операций изменения цвета. а) Опишите корректное красно-черное дерево с и узлами, в котором вызов процедуры КВ 1нзект для вставки (и+ 1)-го узла приводит к П(!8п) изменениям цвета. Затем опишите корректное красно- черное дерево с и узлами, в котором вызов процедуры КВ 13еьете для удаления определенного узла приводит к Й (!8п) изменениям цвета.
Несмотря на то, что в наихудшем случае количество модификаций цветов, приходящихся на одну операцию, может определяться логарифмической функцией, мы докажем, что произвольная последовательность гл операций КВ 1нзект и КВ 1)е!.ете, выполняемых над изначально пустым красно-черном деревом, в наихудшем случае приводит к 0(т) структурным модификациям. б) Некоторые из случаев„обрабатываемых в основном цикле кода процедур КВ 1хзект Р!хаев и КВ 0н.ете Рий3Р, являются завершающими (гепшпайп8): однажды случившись, они вызовут завершение цикла после выполнения фиксированного количества дополнительных операций.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
