Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 112
Текст из файла (страница 112)
509 Глава! 7 Амортизационный анализ 17.4.3 Предположим, что вместо того, чтобы сжимать таблицу, вдвое уменьшая ее размер при уменьшении коэффициента заполнения ниже значения 1/4, мы будем сжимать ее до 2/3 исходного размера, когда значение коэффициента заполнения становится меньше 1/3. С помощью функции потенциала Ф(Т) = ~2.Т.пинг — Т.всве~ покажите, что амортизированная стоимость процедуры ТАвы-(3н.ктл, в кото- рой применяется эта стратегия, ограничена сверху константой. Задачи 17.1. Обратный бинарный битовый счетчик В главе 30 описан важный алгоритм, называемый быстрым преобразованием Фурье (Раас Роппег Тгапз1опп — РРТ).
На первом этапе алгоритма РРТ выполняется обратная перестановка битов (Ь(г-гечегва1 репппгайоп) входного массива А(0 .. и — 1), длина которого равна п = 2" для некоторого неотрицательного целого й. В результате перестановки каждый элемент массива меняется местом с элементом, индекс которого является числом с бинарным представлением, обратным но отношению к бинарному представлению исходного индекса. Каждый индекс а можно представить в виде последовательности зс бит (аь и аь — г,, ао), где а = 2,';:о а, 2'. ОпРеделим опеРацию теть((аь-и аа-г,..., ао) ) = (ао, ап, .., аь г); таким образом, ь-1 теть(а) = ~~в аь, г2' Например, если и = 16 (илн, что эквивалентно, к = 4), то теть(3) = 12, поскольку 4-битовое представление 3 — 0011, которое при обращении дает 1100, 4-битовое представление 12.
вь Пусть имеется функция гечы выполняющаяся в течение времени гз(к). Разработайте алгоритм обратной перестановки битов в массиве длиной и = 2", время работы которого равно 0(п(с). Чтобы улучшить время перестановки битов, можно воспользоваться алгоритмом, основанным на амортизационном анализе. Мы поддерживаем счетчик с обратным порядком битов и процедуру В1т-Квчвкзвп-1мскеыемт, которая для заданного показания счетчика а возвращает значение геть(течь(а) + 1).
Например, если й = 4 и счетчик начинает отсчет от О, то в результате последовательных вызовов Часть 1К усовершенствованные методы разработки и анализа процедуры Вгт-Кечекзегэ-1мсиемемт получим последовательность 0000, 1000, 0100, 1100, 0010, 1010,...
= О, 8, 4, 12, 2, 10, б. Предположим, что слова в компьютере хранятся в виде к-битовых значений и что в течение единичного промежутка времени компьютер может произвести над этими бинарными значениями такие операции, как сдвиг влево или вправо на произвольное число позиций, побитовое И, побитовое ИЛИ и т.п. Опишите реализацию процедуры В1т-йечекзегз-1мскемемт, позволяющую выполнять обращение порядка битов п-элементного массива за время 0(п).
в. Предположим, что в течение единичного промежутка времени слово можно сдвинуть вправо или влево только на один бит. Сохраняется ли при этом возможность реализовать обращение порядка битов в массиве за время О(п)? 17.2. Динамический бинарный поиск Бинарный поиск в отсортированном массиве осуществляется в течение промежутка времени, описываемого логарифмической функцией, однако время вставки нового элемента линейно зависит от размера массива. Время вставки можно улучшить, используя несколько отсортированных массивов. В частности, предположим, что операции Белксц и 1меект должны поддерживаться для и-элементного множества.
Пусть к = ~18(п + 1)~ и пусть бинарное представление числа и имеет вид (пь г, пь з,..., по). У нас имеется к отсортированных массивов Ае, Аг,...,Аь и где для всех 1 = 0,1,..., й — 1 длина массива А, равна 2'. Каждый массив либо заполнен, либо пуст, в зависимости от того, равно ли и, = 1 илн п, = 0 соответственно. Таким обьоазом, полное количество элементов, хранящихся во всех 1с массивах, равно 2',;:а и; 2' = п. Хотя каждый массив отсортирован, между элементами различных массивов нет никаких отношений.
а. Опишите, как реализовать операцию Белксц в этой структуре данных. Проанализируйте время ее работы в наихудшем случае. б. Опишите, как вставлять новый элемент в эту структуру данных. Проанализируйте время выполнения этой операции 1мзект в наихудшем случае и ее амортизированное время работы. в. Подумайте, как реализовать операцию ОЕЕЕТЕ. 17.3. Аморквиэированные сбавансированные по весу деревья Рассмотрим обычное бинарное дерево поиска, расширенное за счет добавления к каждому узлу х атрибута х.везе, содержащего количество ключей, которые хранятся в поддереве с корнем в узле х.
Пусть се — константа из диапазона 1/2 < се < 1. Назовем данный узел х О-сбалансированным (п-йа!апсеб), если х.1еЯ.неве < а х,в1ге и х.пдЫ.вьее < се х.вехе. Дерево в целом является сх-сбалансированнмн, если а-сбалансирован каждый его узел. Описанный ниже 5зз Глава ! Х Амортизационный анализ амортизированный подход к сбалансированным деревьям был предложен Д. Вар- гисом (б.
Чагй?зеве). а В определенном смысле 1/2-сбалансированное дерево является наиболее сбалансированным. Пусть в произвольном бинарном дереве поиска задан узел х. Покажите, как перестроить поддерево с корнем в узле х таким образом, чтобы оно стало 1/2-сбалансированным. Время работы алгоритма должно быть равным лэ(х. взге), а объем используемой вспомогательной памяти — О(х. взге).
6. Покажите, что поиск в бинарном сз-сбалансированном дереве поиска с и узлами в наихудшем случае выполняется за время О(1к п). При выполнении оставшейся части этой задачи предполагается, что константа сз строю больше 1/2. Предположим, что операции ?манят и ?знати реализованы так же, как и в обычном бинарном дереве поиска с и узлами, за исключением того, по после каждой такой операции, если хотя бы один узел дерева не является о-сбалансированным, поддерево с самым высоким несбалансированным узлом "перестраивается" так, чтобы оно стало 1/2-сбалансированным.
Проанализируем эту схему с помощью метода потенциалов. Для узла х, принадлежащего бинарному дереву поиска Т, определим величину 25(х) = 1х,1е/й.азге — х. пдву.азге~ а потенциал дерева Т определим как Ф(Т) = с ~~~ га(х), нет:Сз?в)>2 где с — достаточно большая константа, зависящая от а. ж Докажите, что потенциал любого бинарного дерева поиска всегда неотрицателеи и что потенциал 1/2-сбалансированного дерева равен О.
а Предположим, что т единиц потенциала достаточно для оплаты перестройки полдерева, содержащего т узлов. Насколько большой должна быть константа с, выраженная через сз, чтобы амортизированное время перестройки поддерева, не являющегося о-сбалансированным, было равным О(1)? д. Покажите, что амортизированное время вставки узла в сз-сбалансированное дерево с и узлами, как и удаления узла из этого дерева, равно О(1я и). 17.4.
Стоимость лерестройки красно-черных деревьев Имеется четыре основные операции над красно-черными деревьями, которые выполняют структурные модификации (аппсппа! пюс?1??са6опз); вставка узла, удаление узла, поворот и изменение цвета. Мы видели, что для поддержки свойств красно-черных деревьев в процедурах ??В-?нзнкт и ??В-?)еьнте достаточно использовать О(1) операций поворота, вставки узлов и удаления узлов, но в них требуется намного больше операций изменения цвета. Часть ги усовершенствованные методы разработки и анализа а Опишите корректное красно-черное дерево с и узлами, в котором вызов процедуры КВ-1мзпкт для вставки (и+ 1)-го узла приводит к П(1к гь) изменениям цвета Затем опишите корректное красно-черное дерево с п узлами, в котором к П(1к зз) изменениям цвета приводит вызов процедуры КВ-Ощ.ктп для удаления определенного узла.
Несмотря на то что в наихудшем случае количество изменений цветов, приходящихся на одну операцию, может оказаться логарифмическим, мы докажем, что произвольная последовательность т операций КВ-1мзпкт и КВ-Окькте, выполняемых над изначально пустым красно-черном деревом, в наихудшем случае приводит к 0(тп) структурным изменениям. б. Некоторые из случаев, обрабатываемых в основном цикле кода процедур КВ1мзккт-г1хпр и кВ-Рн.антк-р1х~л', являются заверивающими (зепшпайпй): встретившись, они вызовут завершение цикла после выполнения фиксированного количества дополнительных операций. Установите для каждого случая, встречающегося в процедурах КВ-1мзпкт-г1хпр и КВ-Он.етк-р1хпр, какой из них является завершающим, а какой — нет. (Указание: обратитесь к рис.
13.5-13.7.) Сначала проанализируем структурные модификации для случая, когда выполняются только вставки. Пусть Т вЂ” красно-черное дерево. Определим для него функцию Ф(Т) как количество красных узлов в дереве Т. Предположим, что одной единицы потенциала достаточно для оплаты структурных изменений, выполняемых в любом из трех случаев процедуры КВ-1мзпкт-г1хпр. ж Пусть Т' — результат применения случая 1 из процедуры КВ-1мзккт-Р1хпр к Т. Докажите, что Ф(Т') = Ф(Т) — 1. д.
Воспользовавшись результатами, полученными в п. (г), докажите, что амортизированное количество структурных модификаций, которые выполняются при любом вызове процедуры КВ-1мзккт, равно 0(1). Теперь нам нужно доказать, что если выполняются и вставки, и удаления, то выполняются 0(гл) структурных модификаций. Для каждого узла х определим величину О, если х красный, 1, если х черный и не имеет красных дочерних узлов, О, если х черный и имеет один красный дочерний узел, 2, если х черный и имеет два красных дочерних узла . ьо(х) = * Операцию вставки узла в красно-черное дерево с помощью процедуры КВ1мзект можно разбить на три части. Перечислите структурные модификации и изменения потенциала, которые происходят в результате выполнения строк 1-16 процедуры КВ-1мзпкт для незавершающих случаев процедуры КВ-1мзект-Е~х~л' и для завершающих случаев этой процедуры.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
