Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 104
Текст из файла (страница 104)
(пит; — 1) — визе; з) = = 3. Если же г-я операция ТАв~.н 1нзикт приводит к расширению, то вите; = 2 з1ве; ~ и зквев г = пит; в = пит; — 1, откуда следует, что визе< = 2 (пит; — 1). В этом случае амортизированная стоимость операции будет следующей: с;=с;+Ф; — Ф» г= = пит<+ (2 пит; — зввев) — (2 пит; з — в1ве; ~) = = пит; + (2 пит; — 2 (питв — 1)) — (2 (пит; — 1) — (пит; — 1)) = = пит;+ 2 — (питв — 1) = = 3.
На рис. 17.3 приведена зависимость величин пит;, зйе; и Ф; от г. Величина пит; обозначена тонкой линией, величина ввве; — пунктирной линией и ф;— толстой линией. Обратите внимание, что непосредственно перед расширением потенциал возрастает до значения, равного количеству содержащихся в таблице элементов, поэтому становится достаточным для уплаты за перемещение всех элементов в новую таблицу.
Впоследствии потенциал снижается до нуля, но тут же возрастает до значения 2, югда в таблицу вставляется элемент, вызвавший ее расширение. 17.4.2 Расширение и сжатие таблицы Чтобы реализовать операцию Тлвьн 13и.ете, достаточно просто удалить из нее указанный элемент. Однако часто желательно сжать (соппас~) таблицу, если ее коэффициент заполнения становится слишюм мал, чтобы пространство не расходовалось напрасно. Сжатие таблицы выполняется аналогично ее расширению: если количество элементов в ней достигает некоторой критической нижней отметки, выделяется место для новой, меньшей таблицы, после чего элементы из старой таблицы копируются в новую.
Затем место, используемое для старой таблицы, можно будет освободить путем возвращения его системе управления памятью. В идеале желательно, чтобы выполнялись два свойства: ° юэффициент заполнения динамической таблицы ограничен снизу некоторой константой; Часть!Ч. Усовершенствованные методы разработки н анализа 500 32 24 !6 16 24 32 Рис. 17.3. Зависимость величин иит2 (количество элементов в таблице), 61ге; (количество ячеек в таблице) и потенциала Ф, от количества операций Тальк 1ньвкт ° амортизированная стоимость операций по обработке таблицы ограничена сверху некоторой константой.
Предполагается, что эту стоимость можно измерить в терминах элементарных вставок и удалений. Естественная стратегия при расширении и сжатии таблицы состоит в том, чтобы удваивать ее размер при вставке элемента в заполненную таблицу и в два раза уменьшать его, когда удаление элемента из таблицы приводит к тому, что она становится заполненной меньше чем на половину, При этом гарантируется, что величина коэффициента заполнения таблицы не может быть меньше 1/2.
Однако, к сожалению, это может привести к тому, что амортизированная стоимосп операции станет довольно большой. Рассмотрим такой сценарий. Над таблицей Т выполняется и операций, где и — степень двойки. Первые и/2 операций — операции вставки, и их полная стоимость, согласно нашему предыдущему анализу, равна 6 1п). В конце этой последовательности вставок пит [Т) = в1яе ~Т) = и/2.
В качестве следующих и/2 операций выполним такую последовательность: где 1 обозначает вставку, а 12 — удаление. Первая вставка приводит к расширению таблицы, объем которой равен и. Два следующих удаления вызовут сжатие таблицы обратно до размера п/2. Следующие две вставки приведуг к еще одному расширению и т.д. Стоимость каждого расширения и сжатия равна О (и), Глава 17. Амортизационный анализ 501 н всего их — 9 (п). Таким образом, полная стоимость и операций равна 9 (п~), а амортизированная стоимость одной операции — ~Э (п). Трудность, возникающая при использовании данной стратегии, очевидна: после расширения мы не успеваем выполнить достаточное юличество удалений, чтобы оплатить сжатие.
Аналогично, после сжатия не выполняется достаточное юличество вставок, чтобы оплатить расширение. Эту стратегию можно улучшить, если позволить, чтобы коэффициент заполнения таблицы опускался ниже 1/2. В частности, как и раньше, размер таблицы будет удваиваться прн вставке элемента в заполненную таблицу, но ее размер будет уменьшаться в два раза, если в результате удаления таблица становится заполненной не наполовину, как это было раньше, а на четверть.
При этом коэффициент заполнения таблицы будет ограничен снизу юнстантой 1/4. Идея заключается в том, что после расширения таблицы ее коэффициент заполнения равен 1/2, поэтому перед сжатием необходимо будет удалить половину элементов, поскольку сжатие не будет выполнено до тех пор, пока коэффициент заполнения не станет меньше 1/4. Кроме того, после сжатия коэффициент заполнения таблицы также равен 1/2.
Таким образом, количество элементов таблицы должно быть удвоено путем выполнения вставок перед тем, как сможет произойти расширение, посюльку оно выполняется только в том случае, когда коэффициент заполнения может превысить 1. Код процедуры Тяв1.е Он.ете здесь не приводится, поскольку он аналогичен коду процедуры ТЛВ1.Е 1НЗЕКТ. Однако для анализа удобно предположить, что если количество элементов таблицы падает до нуля, то выделенное для нее пространство освобождается, т.е. если пит [Т) = О, то веге [Т) = О. Теперь можно проанализировать стоимость последовательности из п операций ТАЕ1.е 1нзект и Тлвье Оеьете, воспользовавшись методом потенциалов. Начнем с того, что определим потенциальную функцию Ф, которая равна О сразу после расширения или сжатия, и возрастает по мере того, как коэффициент заполнения увеличивается до 1 или уменьшается до 1/4.
Обозначим коэффициент заполнения непустой таблицы Т через а (Т) = пит [Т]/ваге [Т]. Посюльку для пустой таблицы выполняются соотношения пит [Т] = веге [Т) = О и а (Т) = 1, равенство пит [Т] о (Т) веге [Т) всегда справедливо, независимо от того, является таблица пустой или нет. В качестве потенциальной будет использоваться следующая функция: (2 пит [Т) — взге [Т] при о (Т) > 1/2, (17.6) '(веге [Т]/2 — пит[Т) при гг(Т) ( 1/2. Обратите внимание, что потенциал пустой таблицы равен О и что потенциальная функция ни при каких аргументах не принимает отрицательного значения.
Таким образом, полная амортизированная стоимость последовательности операций для Часть |Ч. Усовершенствованные методы разработки н анализа 502 32 24 !6 8 1б 24 32 40 48 Рис. 17.4. Зависимость величин пип44 (количество элементов в таблице), 44ге4 (количество ячеек в таблице) н потенциала Ф4 от количества операций Тхвьв 1нзвкт и Тхвьв Рвьвте функции Ф является верхней границей фактической стоимости этой последовательности.
Прежде чем продолжить анализ, сделаем паузу для обсуждения некоторых свойств потенциальной функции. Заметим, что когда коэффициент заполнения равен 1/2, потенциал равен О. Когда коэффициент заполнения равен 1, то зхке [Т) = = пит [Т), откуда Ф (Т) = пит [Т], следовательно, значение потенциала оказывается достаточным для оплаты расширения в случае добавления элемента. Если же юэффициент заполнения равен 1/4, то выполняется соотношение а(зе [Т) = 4.
пит [Т), откуда Ф (Т) = 24ит [Т), и в этом случае значение потенциала также является достаточным для оплаты сжатия в результате удаления элемента. Чтобы проанализировать последовательность п операций ТАв~.в 1мзвкт и Тхвьв Рн.втв, обозначим через с; фактическую стоимость г-й операции, через с;— ее амортизированную стоимость в соответствии с функцией Ф, через пит4— юличество хранящихся в таблице элементов после выполнения г-й операции, через зхзе4 — полный обьем таблицы после выполнения г-й операции, через а;— коэффициент заполнения таблицы после выполнения г-й операции и через Фб— потенциал после выполнения 4-й операции.
Изначально пито = О, зхвео = О, оо = 1 и Фо = О. На рис. 17.4 проиллюстрировано поведение потенциала при выполнении последовательности операций. Величина пит; обозначена тонкой линией, величина зхзе; — пунктирной линией и величина Фб — толстой линией. Обратите внимание, что непосредственно перед расширением потенциал возрастает до значения, равного юличестьу содержащихся в таблице элементов, поэтому становится доста- Глава 17. Амортизационный анализ 503 точным для уплаты за перемещение всех элементов в новую таблицу. Аналогично, непосредственно перед сжатием потенциал тоже достигает значения, равного количеству элементов таблицы.
Начнем со случая, когда г-й по счету выполняется операция Тлвьн 1нзнкт. Если сн з > 1/2, то этот анализ идентичен тому, который был проведен в разделе 17.4.1 для расширения таблицы. Независимо от того, расширяется таблица или нет, амортизированная стоимость с; операции не превышает 3. Если сн ~ < < 1/2, таблицу нельзя расширить в результате выполнения операции, поскольку расширение происходит только когда ол з = 1. Если, кроме того, си < 1/2, то амортизированная стоимость г-й операции равна с;=с;+Ф,— Ф; ь= = 1+ (звге;/2 — пит,) — (ввге; з/2 — пит; в) = = 1 + (вгге;/2 — пит;) — (зкге;/2 — (пит; — 1)) = = О. Если сн з < 1/2, но сн > 1/2, то с,+Ф; — Ф, ь= 1+ (2.
пит; — веге; ) — (вгге; з/2 — пит; ~) = 1+(2 (пит, в+1) — з1ге; з) — (згге; в/2 — пит; з) 3 3 пит; ~ — — вгге; з+3 = 3 Зон ~ звге; з — — вгге; з+3 < 3, 3 — ввге; з — — згге; в+2 = 3. Таким образом, амортизированная стоимость операции Тлвнн 1нзнкт не превышает 3. Теперь обратимся к случаю, когда Гнй по счету выполняется операция Тлвпн Ра.нтн.
В этом случае пит; = пит; з — 1. Если си з < 1/2, то необходимо анализировать, приведет ли эта операция к сжатию матрицы. Если нет„то выполняется условие згге; = звге; ы а амортизированная стоимость операции равна с;=с;+Ф; — Ф; з= = 1+ (звге;/2 — пит;) — (з1ге; ~/2 — пит, з) = = 1 + (звге;/2 — пит;) — (згге;/2 — (пит; + 1)) = Часть 1Ч. Усовершенствованные методы разработки н анализа 504 Если си д < 1/2 и г-я операция приводит к сжатию, то фактическая стоимость операции равна с; = питз + 1, поскольку один элемент удаляется и пит; элементов перемешается. В этом случае вЫе;/2 = вике! 1/4 = пит, 1 = пит; + 1, и амортизированная стоимость операции равна оп=с;+Ф! — Ф, з= = (пит;+ 1) + (взве!/2 — пипи) — (вьае; з/2 — пит; !) = = (пит; + 1) + ((пити; + 1) — пит,) — Я2 ° пит; + 2) — (пит! + 1)) = = 1. Если г-я операция — Тлв~.е Ра.нте и выполняется неравенство си 1 > 1/2, то амортизированная стоимость также ограничена сверху константой.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
