Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 111

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 111)

Предполагается, что зту стоимость можно измерить в терминах элементарных вставок и удалений. Естественная стратегия при расширении и сжатии таблицьз состоит в том, чтобы удваивать ее размер при вставке элемента в заполненную таблицу и в два раза уменьшать его, когда удаление элемента из таблицы приводит к тому, что она становится заполненной меньше чем наполовину.

При этом гарантируется, что величина коэффициента заполнения таблицы не может быть меньше 1/2. Однако, к сожалению, это может привести к тому, что амортизированная стоимость операции станет довольно большой. Рассмотрим такой сценарий. Над таблицей Т выполняется и операций, где и — степень двойки. Первые и/2 операций — операции вставки, и их полная стоимость, согласно нашему предыдущему анализу, равна лз(п). В конце этой последовательности вставок Т. ззипз = Т. визе = и/2.

В качестве следующих и/2 операций выполним такую последовательность: вставка, удаление, удаление, вставка, вставка, удаление, удаление, вставка, вставка, ... Первая вставка приводит к расширению таблицы, объем которой равен и. Два следующих удаления вызовут сжатие таблицы обратно до размера и/2. Следующие две вставки приведут к еше одному расширению и т.д. Стоимость каждого расширения н сжатия равна 9(п), а всего их — 9(п). Таким образом, полная стоимость и операций равна 9(п ), а амортнзированная стоимость одной операции — 9(п).

Трудность, возникающая при использовании данной стратегии, очевидна: после расширения мы не успеваем выполнить достаточное количество удалений, чтобы оплатить сжатие. Аналогично после сжатия не выполняется достаточное количество вставок, чтобы оплатить расширение.

Эту стратегию можно улучшить, если позволить, чтобы коэффициент заполнения таблицы опускался ниже 1/2. В частности, как и раньше, размер таблицы будет удваиваться при вставке элемента в заполненную таблицу, но ее размер будет уменьшаться в два раза, если в результате удаления таблица становится заполненной не наполовину, как это было раньше, а на четверть.

Прн этом коэффициент заполнения таблицы будет ограничен снизу константой 1/4. Интуитивно мы рассматриваем коэффициент заполнения 1/2 как идеальный, а потенциал таблицы при этом равен О. При отклонении коэффициента заполнения от 1/2 потенциал возрастает таким образом, чтобы к тому времени, когда мы будем расширять или сжимать таблицу, его было достаточно, чтобы оплатить копирование всех элементов во вновь выделенную таблицу. Таким образом, нам потребуется функция потенциала, которая растет до Т. ппш, когда коэффициент заполнения либо возрастает до 1, либо уменьшается до 1/4. После как сжатия, так н расширения таблицы коэффициент заполнения становится равным 1/2, а потенциал таблицы обнуляется.

Часть 1К 'зсовершенствованные методы разработки и анализа Код процедуры ТАвее-Рееете здесь не приводится, поскольку он аналогичен коду процедуры ТАв~.е-1ызект. Однако для анализа удобно предположить, что если количество элементов таблицы уменьшается до нуля, то выделенное для нее пространство освобождается, т.е. если Т. питп = О, то Т, вьее = О. Теперь можно проанализировать стоимость последовательности из п операций ТАВее-1ызект и ТАвее-гэееете, воспользовавшись методом потенциалов.

Начнем с того, что определим функцию потенциала Ф, которая равна О сразу после расширения или сжатия и возрастает по мере того, как юэффициент заполнения увеличивается до 1 или уменьшается до 1/4. Обозначим коэффициент заполнения непустой таблицы Т через а(Т) = Т. пит/Т.вззе. Поскольку для пустой таблицы выполняются соотношения Т. пит = Т. иге = О и а(Т) = 1, равенство Т. пит = а(Т) Т. вьзе всегда справедливо, независимо от того, является ли таблица пустой. В качестве функции потенциала будет использоваться следующая: ) 2.

Т,пит — Т.тле, если а(Т) ) 1/2, ). Т. вгае/2 — Т. пит, если а(Т) < 1/2 . Обратите внимание, что потенциал пустой таблицы равен О и что функция потенциала ни при каких аргументах не принимает отрицательного значения. Таким образом, полная амортизированная стоимость последовательности операций для функции Ф является верхней границей фактической стоимости этой последовательности.

Прежде чем продолжить точный анализ, сделаем паузу для обсуждения некоторых свойств функции потенциала, проиллюстрированной на рис. 17.4. Заметим, что когда коэффициент заполнения равен 1/2, потенциал равен О. Когда коэффициент заполнения равен 1, выполняется соотношение Т.згяе = Т. пит, откуда вытекает Ф(Т) = Т. пит, следовательно, значение потенциала оказывается достаточным для оплаты расширения в случае добавления элемента.

Если же юэффициент заполнения равен 1/4, выполняется соотношение Т.зме = 4 Т.пит, откуда следует Ф1,Т) = Т. пит, и в этом случае значение потенциала также является достаточным для оплаты сжатия в результате удаления элемента. Чтобы проанализировать последовательность и операций ТАвее-1ызект и ТАвее-Овеете, введем следующие обозначения: обозначим через с; фактическую стоимость 1-й операции, через с; — ее амортизнрованную стоимость в соответствии с функцией Ф, через пит, — юличество хранящихся в таблице элементов после выполнения в'-й операции, через в1зе1 — полный объем таблицы после выполнения 1-й операции, через а; — коэффициент заполнения таблицы после выполнения 1-й операции и через Ф, — потенциал после выполнения 1-й операции.

Изначально пито = О, ввзео = О, ае = 1 и Фо = О. Начнем со случая, когда 1-й по счету выполняется операция ТАвее-1мзект. Если а; 1 > 1/2, то этот анализ идентичен тому, который был проведен в разделе 17.4.1 для расширения таблицы. Независимо от того, расширяется таблица нли нет, амортизированная стоимость с; операции не превышает 3.

Если а, 1 < 1/2, таблица не может быть расширена в результате выполнения операции, поскольку расширение происходит только тогда, югда а; 1 = 1. При а, < 1/2 амортизиро- 507 Глава /7. Амортизационный анана 32 1б О О 8 1б 24 32 40 48 Рвс. 17.4. Влияние последовательности и операций Тлньн-1нвнкт и Тлнсн-Онснтн на количество пит, элементов в таблице, количество взле, ячеек таблицы и потенциал Ф,= 2. пит, — вас,, если а, > 1/2, =( .' вые,/2 — пит,, если си < 1/2, измеренные после кшкдой а-й операции.

Величина пит, показана тонкой линией, взве, — пунктирной, а Ф, — толстой линией. Обраппе внимание, что непосредственно перед расширением потенциал возрастает до значения, равного количеству содержшцихся в таблице элементов, поэтому становится достаточным для оплаты перемещения всех элементов в новую таблицу. Аналогично непосредственно перед сжатием потенциал также возрастает до значения, равного количеству содерж авлсюя в таблице элементов.

ванная стоимость зьй операции ранна с,=с;+Ф,— Ф, 1 = 1+ (язве;/2 — пит,) — (вале; 1/2 — пит; 1) = 1+ (вале;/2 — пит,) — (вале;/2 — (питз — 1)) =О. Если си 1 ( 1/2, носи ) 1/2, имеем с,+Ф; — Ф, 1 1+ (2 ° пит, — ваде;) — (взлез 1/2 — пит; 1) 1+ (2(пит; 1+1) — вале; 1) — (взвев 1/2 — пит; 1) 3 3 пит, 1 — -велев 1+3 3 Зои 1взге; 1 — -вале; 1+3 3, 3, -ялеа 1 — -взвее 1+3 3. 500 Часть ГК зссоверсненствованные методы разработки и анавиза Таким образом, аморгизированная стоимость операции Тлвьл-1мзлкт не превышает 3. Теперь обратимся к случаю, когда 1-й по счету выполняется операция Тлвыгзег.ете. В этом случае пят, = пита; 1 — 1.

Если сп 1 < 1/2, то необходимо анализировать, приведет ли эта операция к сжатию матрицы. Если нег, выполняется условие шее, = вите, н и амортизированная стоимость операции равна с,=с,+Ф; — Ф, 1 = 1+ (вьее,/2 — пипи) — (вьеее 1/2 — пят, з) = 1+ (вьее,/2 — пить) — (вьеее/2 — (пот, + 1)) =2. Если се, 1 < 1/2 и 1-я операция приводит к сжатию, то фактическая стоимость операции равна с; = пят, + 1, поскольку один элемент удаляется и пит, элементов перемешается. В этом случае аьее,/2 = велес 1/4 = пить 1 = пить + 1, и амортизированная стоимость операции равна с,.=с;+Ф,— Ф; 1 = (пит, + 1) + (вкее,/2 — пиеа;) — (вьеес 1/2 — пяте 1) = (пит, + 1) + ((пит, + 1) — пит,) — ((2 . пшпз + 2) — (лилье + 1)) =1.

Если 1-я операция — Тлвье-Ре1.ете и выполняется неравенство сц 1 ) 1/2, то амортизированная стоимость также ограничена сверху константой. Анализ этого случая предлагается выполнить в упр. 17.4.2. Подведем итог. Поскольку амортизированная стоимость каждой операции ограничена сверху константой, фактическая стоимость выполнения произвольной последовательности из и операций над динамической таблицей равна О(п). Упражнения 17.4.1 Предположим, что нужно реализовать динамическую хеш-таблицу с открытой адресацией.

Почему может понадобиться считать такую таблицу заполненной, когда ее коэффициент заполнения достигнет некоторого значения се, строго меньшего 1? Кратко опишите, как следует выполнять вставки в динамическую хеш-таблицу с открытой адресацией, чтобы математическое ожидание амортизированной стоимости вставки было равно О(1). Почему математическое ожидание фактической стоимости вставки может быть равным О(1) не для всех вставок? 17.4.2 Покажите, что если ск, 1 > 1/2 и 1-я операция, выполняющаяся над динамической таблицей, — Тли~.е-Ре1.рте, то амортизированная стоимость операции для функции потенциала (17.б) ограничена сверху константой.

Характеристики

Список файлов книги