Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 110
Текст из файла (страница 110)
Амортизационный анпзиз эквивалентно) когда ее коэффициент заполнения становится равным 1'. В некоторых программных средах при попытке вставить элемент в заполненную таблицу не остается ничего другого, как прибегнуть к аварийному завершению программы, сопровождаемому выдачей сообщения об ошибке. Однако мы предполагаем, что наша программная среда, подобно многим современным средам, обладает системой управления памятью, позволяющей по запросу выделять и освобождать блоки памяти. Таким образом, когда в заполненную таблицу вставляется элемент, ее можно растырить (ехрапд), выделив место для новой таблицы, содержащей больше ячеек, чем было в старой. Поскольку таблица всегда должна размещаться в непрерывной области памяти, для большей таблицы необходимо выделить новый массив, а затем скопировать элементы из старой таблицы в новую.
Общепринятый эвристический подход заключается в том, чтобы в новой таблице было в два раза больше ячеек, чем в старой. Если в таблицу элементы толью вставляются, то значение ее коэффициента заполнения будет не меньше 17г2, поэтому обьем неиспользованного места никогда не превысит половины полного размера таблицы. В приведенном ниже псевдокоде предполагается, что Т вЂ” объект, представляющий таблицу. Атрибут Т.1айе содержит указатель на блок памяти, представлякнций таблицу. В Т.пит содержится количество элементов в таблице, а в Т.ззхе — полное количество ячеек в таблице. Изначально таблица пустая: Тпит = Т.згяе = О.
Тлвее-1ыбект (Т, х) 1 1ТТ.ззде == О 2 Выделить Т, !аЫе с 1 ячейкой 3 Т.зыке = 1 4 И'Т.пизп == Т.визе 5 Выделить пеиг-!а6(е с 2. Т.згае ячейками б Вставить все элементы из Т. 1айе в пеиг-1айе 7 Освободить Т. $айе 8 Т.Фа61е = пеиг-1аЫе 9 Т.зззе = 2 Т.йхе 10 Вставить х в Т. !аЫе 11 Т.пизп = Т.пигп+ 1 Обратите внимание, что здесь имеется две "вставки" (сама процедура Тлвее1нзвкт и операция элементарной вставки (е!ешепгагу 1пзегг(оп) в таблицу), выполняемые в строках б и 10. Время работы процедуры Тлвее-1)4зект можно проанализировать в терминах количества элементарных вставок, считая стоимость каждой такой операции равной 1.
Предполагается, что факгичесюе время работы процедуры Тлвее-1)цбент линейно зависит от времени вставки отдельных эле- гв некоторых случках, например при работе с хеппгрованиымн таблнпами а открытой адреавпией, монет поиадобитьаа считать твблипу заполненной, если ее козффипиент заполненив равен некоторой конатантс, строго меньшей 1. (См. упр. 17Л.1.) Часть ГК усовершенствованные методы разработки и анализа ментов, так что накладные расходы на выделение исходной таблицы в строке 2— константа, а накладные расходы на выделение и освобождение памяти в строках 5 и 7 пренебрежимо малы по сравнению со стоимостью переноса элементов в строке 6.
Назовем расивирением (ехрашйоп) событие, при котором выполняются строки 5-9. Проанализируем последовательность и операций Тлвее-1хзект, которые выполняются над изначально пустой таблицей. Чему равна стоимость с, 1-й операции? Если в данный момент в таблице имеется свободное место (или если это первая операция), то с, = 1, поскольку достаточно выполнить лишь одну элементарную операцию вставки в строке 10. Если же таблица заполнена и нужно выполнить ее расширение, то с, = з: стоимость равна 1 для элементарной вставки в строке 10 плюс з — 1 для элементов, которые необходимо скопировать из старой таблицы в новую (строка 6). Если выполняется п операций, то стоимость последней из них в наихудшем случае равна О(п), в результате чего верхняя граница полного времени выполнения и операций равна О(п ). Эта оценка является неточной, поскольку при выполнении и операций ТЛЕЕЕ1мзект потребность в расширении таблицы возникает не так часто.
Точнее говоря, 1-я операция приводит к расширению, только если величина з — 1 равна степени 2. С помощью группового анализа можно показать, что амортизированная стоимость операции в действительности равна О(1). Стоимость 1-й операции равна з, если з — 1 является точной степенью 2, с; = т 1 в противном случае . Таким образом, полная стоимость выполнения и операций Тлеее-1мзект равна и рк и) с, <и+ ~~з 2з з=о (о+2п =Зл, поскольку стоимость не более п операций равна 1, а стоимости остальных операций образуют геометрическую прогрессию. Поскольку полная стоимость п операций Тлнее-1мзект ограничена величиной Зп, амортизированная стоимость одной операции не превышает 3. С помощью метода бухгалтерского учета можно показать "на пальцах", что амортизированная стоимость операции Тяп~.Е-!мЕЕкт должна быть равна 3. Интуитивно понятно, что для каждого элемента приходится трижды платить за элементарную операцию вставки: за саму вставку в текущую таблицу, за перемещение этого элемента при расширении таблицы и за перемещение еще одного элемента, который уже однажды был перемещен в ходе расширения таблицы.
Например, предположим, что сразу после расширения таблицы ее размер становится равным пз. Тогда количество элементов в ней равно т/2 и таблице соответствуег нулевой кредит. На каждую вставку начисляется по 3 доллара. Элементарная 103 Глава 17. Амортизационный аз~ил вставка, которая выполняется тут же, стоит 1 доллар. Еше 1 доллар зачисляется в кредит на вставляемый элемент. Третий доллар зачисляется в качестве кредита на один из уже содержащихся в таблице т/2 элементов.
Для заполнения таблицы требуется т/2 — 1 дополнительных вставок, поэтому к тому времени, когда в таблице будет т элементов и она станет заполненной, каждому элементу будет соответствовать доллар, предназначенный для оплаты его перемещения в новую таблицу в процессе расширения. Анализ последовательности из и операций ТАВее-1ызект можно выполнить в с помощью метода потенциалов. Этим мы сейчас и займемся; кроме того, этот метод будет использован в разделе 17.4.2 для разработки операции ТАВЕЕВЕЬЕтЕ, амортизированная стоимость которой равна О(1).
Начнем с того, что определим функцию потенциала Ф, которая становится равной О сразу после расширения и достигает значения, равного размеру матрицы, к тому времени, когда матрица станет заполненной. В этом случае предстоящее расширение можно будет оплатить за счет потенциала. Одним из возможных вариантов является функция Ф(Т) = 2 Т.пит — Т.згге (17.5) Сразу после расширения выполняется соотношение Т.
пит = Т. злге/2, поэтому, как и требуется, Ф(Т) = О. Непосредственно перед расширением справедливо равенство Т. пит = Т. з)ге, следовательно, как и требуется, Ф(Т) = Т. пит. Начальное значение потенциала равно О, и, поскольку таблица всегда заполнена не менее чем наполовину, выполняется неравенство Т. пит > Т, злге/2, из которого следует, что функция Ф(Т) всегда неотрицательна. Таким образом, суммарная амортизированная стоимость п операций ТАВЕЕ-1ЫЗЕКт является верхней границей суммарной фактической стоимости.
Чтобы проанализировать амортизированную стоимость 1-й операции ТАВее1ынект, обозначим через пит, количество элементов, хранящихся в таблице после этой операции, через з1гез — общий размер таблицы после этой операции л через Ф, — потенциал после этой операции. Изначально пито = О, зггео = О нФо=О. Если 1-я операция ТАвее-1ызект не приводит к расширению, то з1ге; зме, з и амортизированная стоимость операции равна с,=с,+Ф,— Ф, 1 = 1+ (2.
пит; — зьге,) — (2 пит, з — з(ге; 1) = 1+ (2 пит, — згге,) — (2(пит; — 1) — з(ге,) =3. Если же 1-я операция ТАВее-1хзект приводит к расширению, то злге, = 2 зыел 1 низе; 1 = пит, 1 = пит,— 1, откуда вытекает, что злге, = 2 (пит,— 1). Таким Часть 1К Усовершелсшеоеамлые мешады разработки л анализа 504 32 24 1б О ! О 8 16 24 32 Рнс. 17.3. Влияние последовательности и операций Тлвьп-1мзлкт на колнчество лпш, элементов в таблице, количество ыле, ячеек таблнцы н потенциал Ф, = 2 пнт, — яме„ лзмеренные после каждой 1-й операции. Величина пнт, показана тонкой линией, величина ззге, — пунктирной линией, а Ф, — толстой линией. Обратите внимание, что непосредственно перед расширением потенцнал возрастает до значения, равного количеству содержащихся в таблице элементов, поэтому становится достаточным для оплаты перемещення всех элементов в новую табпнцу.
Впоследствии потенциал снижается до О, но туг же возрастает до значения 2, когда в таблицу вставляется элемент, вьпвавшнй ее расширение. образом, амортнзнрованная стоимость операции равна с,=с,+Фз — Ф, 1 = пит; + (2. цит, — лике,) — (2.
пит; 1 — лале, 1) = пит;+(2 пигпз — 2 (питз — 1)) — (2(пит, — 1) — (питз — 1)) = пит, + 2 — (пит; — 1) На рис. 17.3 изображены зависимости значений пито лале, и Ф; от з. Обратите внимание на возрастание потенциала для оплаты расширения таблицы. 17.4.2. Расширение и сжатие таблицы Чтобы реализовать операцию Тлвьб-13н.бтн, достаточно просто удалить из нее указанный элемент. Однако часто желательно сжаяаь (сопггас1) таблицу, если ее коэффициент заполнения становится слишком мал, чтобы пространство не расходовалось напрасно.
Сжатие таблицы выполняется аналогично ее расширению: если количество элементов в ней достигает некоторой критической нижней отметки, выделяется место для новой, меньшей таблицы, после чего элементы нз старой таблицы копируются в новую. Затем место, используемое для старой таблицы, можно будет освободить путем возвращения его системе управления памятью. В идеале желательно, чтобы выполнялись два условия: 505 Глава 1Х Амортизационный анализ коэффициент заполнения динамической таблицы должен быль ограничен сни- зу некоторой положительной константой; амортизированная стоимость табличных операций должна быть ограничена сверху некоторой константой.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
