Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 113
Текст из файла (страница 113)
тзааз !7. Амортизационный анализ 5!3 Теперь переопределим потенциал красно-черного дерева Т как Ф(Т) = ~~~ зо(х) аЕТ н обозначим через Т' дерево, получаемое в результате применения любого незавершающего случая процедуры КВ-1мзякт-Е[хг!р или КВ-Рвьвте-Р!хг!г к дереву Т. е. Покажите, что для всех незавершающих случаев процедуры КВ-1МЗНКтр!Х!5Р выполняется неравенство ф(Т') < ф(Т) — 1. Докажите, что амортизированное количество структурных модификаций, которые выполняются в произвольном вьпове процедуры кВ-1мзвкт-р!хг5Р, равно 0(1). ие. Покажите, что для всех незавершающих случаев процедуры КВ-Рн.етег!хг!р выполняется неравенство Ф(Т') < Ф(Т) — 1.
Докажите, что амортизированное количество структурных модификаций, которые выполняются в произвольном вызове процедуры КВ-Ркптв-р!хл, равно 0(1). з. Завершите доказательство того, что в наихудшем случае в ходе выполнения произвольной последовательности т операций КВ-1мзвкт и КВ-Рвьвтв выполняется 0(т) структурных модификаций. 17.5. Конкурентный анализ самоорганизующихсл снискав с перемещением в начало Самоорганизующийсл список (зе1Г-огйапгкшй 1Ы) представляет собой связанный список из п элементов, в котором каждый элемент имеет уникальный ключ. Поиск в списке заключается в поиске элемента с заданным ключом.
Самоорганнзуюшийся список обладает двумя важными свойствами. 1. Для поиска в списке элемента с заданным ключом требуется пройти по списку от его начала до тех пор, пока не встретится элемент с искомым ключом. Если зто к-й от начала списка элемент, то стоимость его поиска равна !а. 2. Можно переупорядочивать элементы списка после любой операции в соответствии с некоторым правилом и определенной стоимостью. Можно выбрать любую эвристику для принятия решения о том, как именно переупорядочивать список.
Предположим, что мы начинаем работу с заданнопз списка с и элементами, и при этом задана последовательность о = (оз, оз,..., о ) искомых ключей (поиск выполняется в указанном порядке). Стоимостью последовательности является сумма стоимостей отдельных поисков в последовательности. Помимо различных возможных способов переупорядочения списка после операции, в данной задаче рассматривается обмен местами соседних элементов списка (с единичной стоимостью каждой такой операции).
Применив функцию потенциала„необходимо показать, что определенная эвристика переупорядочения 1з за, ззза 514 Часть !и Усовершенствованные методы разраоотни и аниеиза списка (в данном случае — перемещение элемента в начало) имеет общую стоимость, не более чем в 4 раза превышающую стоимость любой иной эвристики для поддержания упорядочения списка — даже если этой эвристике заранее известна последовательность поисков! Этот тип анализа называется конкурентным анализом.
Обозначим для заданной эвристики Н и заданного начального упорядочения списка стоимость последовательности поисков а как Сн(а). Пусть т — количество поисков в последовательности а. а. Докажите, что если эвристике Н список поиска заранее не известен, то стоимость эвристики Н для последовательности а в наихудшем случае равна Сн(а) = П(тп). В случае эвристики перемещения в начало непосредственно после того, как найден искомый элемент х, он перемещается в первую позицию списка (т.е. в его начало). Обозначим ранг элемента х в списке Т, (т.е. его позицию в списке) через галль(х). Например, если х является четвертым элементом в Е,, то гап)сг.
(х) = 4. Обозначим через с, стоимость поиска аз с применением эвристики перемещения в начало, которая включает стоимость поиска элемента в списке и стоимость его перемещения в начало списка путем ряда обменов соседних элементов списка. б. Покажите, что если оч находит элемент х в списке Е с применением эвристики перемещения в начало, то с; = 2 . гап(сс. (х) — 1. Теперь сравним перемещение в начало с любой другой эвристикой Н, которая обрабатывает последовательность поисков в соответствии со сформулированными выше свойствами.
Эвристика Н может обменивать элементы в списке любым способом и даже может знать всю последовательность поисков заранее. Пусть Ь; — список после поиска оч с использованием перемещения в начало, а Ц вЂ” список после поиска а, с использованием эвристики Н. Обозначим стоимость поиска од как с, в случае перемещения в начало, и как с,' — в случае эвристики Н. Предположим, что эвристика Н выполняет ~,* обменов в процессе поиска аь в.
В п. (б) вы показали, что с, = 2 гап(сь,,(х) — 1. Теперь покажите, что с,' = гап(сь;, (х) + ~,*. Определим инверсию в списке Ь, как пару элементов у и е, такую, что у предшествует е в Ц, а г предшествует у в списке Е,*. Предположим, что после обработки последовательности поисков (аы аз,..., а,) список Ц имеет д, инверсий. Тогда мы определим функцию потенциала Ф, которая отображает Е; на действительное число следующим образом: Ф(Е,) = 2д,. Например, если Е, имеет элементы (е,с,а,й, Ь), а Ез имеет элементы (с,а, Ь,с(,е), то Е, имеет 5 инверсий ((е,с),(е,а),(е,с(),(е, Ь), (д,Ь)), так что Ф(Та) = 10.
Заметим, что Ф(Ь,) ) 0 для всех г н что, если эвристика перемещения в начало и зврнстика Н начинают работу с одного и того же списка Ео, Ф(Ео) = О. Глава 17. Амортизационный анализ 515 а Докажите, что обмены либо увеличивают потенциал на 2, либо уменьшают на 2. Предположим, что в результате поиска лг, найден элемент х. Чтобы понять, как в результате поиска с; изменится потенциал, разделим элементы, отличные от х, на четыре множества, в зависимости от того, где они находятся в списке непосредственно перед з'-м поиском.
Множество А состоит из элементов, предшествующих х как в Ь, ы так и в Е,*,. Множество В состоит из элементов, предшествукнцих х в Ц л и следующих захар,* и Множество С состоит из элементов, следующих за х в Е, г и предшествующих ему в Е,* и Множество Р состоит нз элементов, следующих за х как в Б, м так и в Е,",. д, Докажите, что гап1сь,,(х) =1А(+1В)+ 1 игала, (х) = ~А)+ ~С)+1.
е. Покажите, что поиск оч приводит к изменению потенциала Ф(Ь,) — Ф(Ь, 1) < 2(1А~ — 1В~ + г,'), где, как и ранее, эвристика Н выполняет 1; обменов в процессе поиска сь Определим амортизированную стоимость с, поиска оч как с, = с1 + Ф(1„)— Ф(Ь, 1). ж. Покажите, что амортизированная стоимость с, поиска и, ограничена сверху величиной 4с,'. х Сделайте вывод о том, что стоимость Сыто(лг) последовательности поисков вг с перемещением в начало превышает стоимость Сгг(а) последовательности а с применением любой другой эвристики Н не более чем в 4 раза, в предположении, что обе эвристики начинают работу с одним и тем же списком. Заключятельные замечания Групповой анализ был использован Ахо (АЬо), Хопкрофтом (Норсгой) и Ульманом (\ЛЬпап) (5) для определения времени работы операций над лесом непересекающихся множеств; мы будем анализировать эту структуру данных с применением метода потенциалов в главе 21.
Таржан (Тяпал) (329] представил обзор разновидностей метода бухгалтерского учета и метода потенциала, использующихся в амортизационном анализе, а также некоторые их приложения. Метод бухгалтерского учета он приписывает нескольким авторам, включая М. Брауна (М. Вготцп), Таржана, С. Хаддельстона (Я. НнсЫе!згоп) и К. Мельхорна (К. МеИЬогп). Метод 51б Часть 1К Усовершенствованные тетоди разработки и анизиза потенциала он приписывает Д.Д. Слитору (Р.Р.
Б1еа1ог). Термин "амортизационный" вошел в обиход благодаря Слитору и Таржану. Функции потенциалов оказываются полезными также при доказательстве нижних границ в задачах определенных типов. Для каждой конфигурации, возникающей в такой задаче, определяется функция потенциала, отображающая эту конфигурацию на действительное число. После этого определяется потенциал Фы, начальной конфигурации, потенциал Фаны конечной конфигурации и максимальное изменение потенциала ЬФ в результате выполнения произвольного шага. Таким образом, число шагов должно быть не меньше (Фа„,~ — Ф,„;,) /1ЬФ !. Примеры использования функций потенциалов для обоснования нижних границ при оценке сложности ввода-вывода представлены в работах Кормена (Соппеп), Сандквиста (Яппй~шзг) и Вишневски (%1зшезизЫ) [781, Флойда (г)оуд) [106), а также Аггарвала (Акяагьиа!) и Виттера (Ч(цег) [31. Крумм (Кгппнпе), Цыбенко (СуЬетйо) и Венкатараман (Чеп(га1агашап) [2201 воспользовались потенциальными функциями для оценки нижних границ скорости распространения слухов (коза)р(пй): передачи единственного элемента из каждой вершины графа во все другие вершины.
Эвристика перемещения в начало из задачи 17.5 достаточно хорошо работает на практике. Более того, если при обнаружении элемента мы можем поместить его в начало списка за константное время, то можно показать, что стоимость эвристики перемещения в начало превышает стоимость любой иной эвристики не более чем в два раза, даже если этой эвристике весь список поисков известен заранее. Введение В зтой части мы возвращаемся к изучению структур данных, поддерживающих операции над динамическими множествами, но уже на более высоком уровне, чем в части 1П.
В двух первых главах зтой части мы, например, будем использовать технологии амортизационного анализа, которые рассматриваются в главе 17. В главе 18 мы рассмотрим В-деревья, которые представляют собой сбалансированные деревья поиска, разработанные специально для хранения информации на дисках. Поскольку дисковые операции существенно медленнее, чем работа с оперативной памятью, производительность В-деревьев определяется не только временем, необходимым для проведения вычислений, но и количеством необходимых дисковых операций.
Для каждой операции с В-деревом количество обращений к диску растет с ростом высоты В-дерева, так что мы должны поддерживать ее небольшой. В главе !9 рассматривается реализация объединяемых пирамид (тегйеаЫе Беар), которые поддерживают операции 1р!еект, Мцч!Мим, Ехтклст-Мцч и Пр!!о!я.! Процедура 11!ч!он сливает, или объединяет, две пирамиды. Пирамиды Фибоначчи — структуры данных из главы 19 — также поддерживают операции Пекете и Пескелее-Кеу. Для определения производительности фибоначчиевых пирамид мы используем амортизированные границы времени выполнения операций.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
