Ремонт принтеров, сканнеров, факсов и остальной офисной техники


назад Оглавление вперед




[118]

учётная стоимость, причем эти стоимости могут быть как больше, так и меньше реальных. Если учетная стоимость превосходит реальную, разность рассматривается как резерв (credit), который считается связанным с каким-то объектом структуры данных и рассматривается как предоплата за будущую обработку этого объекта. За счет этого резерва компенсируется разница между учетной и реальной стоимостью для тех операций, у которых учетная стоимость ниже реальной.

Мы должны выбирать учётные стоимости так, чтобы фактическая стоимость не превосходила суммы учетных стоимостей, то есть чтобы резерв оставался неотрицательным в любой момент работы.

Операции со стеком

Проиллюстрируем метод предоплаты на уже известном примере со стеком. Напомним, что реальные стоимости операций со стеком мы считаем такими:

Multipop min(s,

где к - количество элементов, удаляемых из стека, s - размер стека. Присвоим этим операциям такие учётные стоимости:

Multipop 0.

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

Покажем теперь, что выбранные нами учетные стоимости позволяют полностью покрыть реальную стоимость операций со стеком. Будем считать, что единицей стоимости операций является доллар. Воспользуемся аналогией между стеком и стопкой тарелок (см. разд. 11.1). Первоначально ни одной тарелки в стопке нет (мы начинаем с пустого стека). Когда мы добавляем тарелку к стопке, мы должны заплатить 1 доллар за операцию Push (это ее реальная цена). Один доллар остается у нас в резерве, ведь учётная цена операции Push равна двум долларам. Будем всякий раз класть этот резервный доллар на соответствующую тарелку. Тогда в каждый момент на каждой тарелке в нашей стопке будет лежать по долларовой бумажке.

Доллар, лежащий на тарелке, - это предоплата за удаление тарелки из стопки. Когда мы производим операцию Pop, мы за нее ничего дополнительно не платим (учётная стоимость Pop равна

Push Pop

1 1

Push Pop

2 0


нулю), а расплачиваемся за удаление тарелки лежащим на ней резервным долларом. Точно так же мы имеем возможность объявить операцию Multipop бесплатной: если надо удалить к тарелок, за удаление каждой из них мы расплатимся лежащим на ней долларом. Стало быть, избыточная плата, которую мы берем за операцию Push, покрывает расходы на операции Pop и Multipop. (стоимость любой последовательности из п операций Push, Pop и Multipop не превосходит суммарной учётной стоимости).

Двоичный счётчик

Решим таким же способом задачу о двоичном счётчике. Нам надо провести амортизационный анализ последовательности из п операций Increment (в исходном состоянии в счетчике записан нуль). Мы уже отмечали, что время работы этой операции пропорционально суммарному количеству установок и очисток битов. Будем считать, что каждая установка или очистка стоит 1 доллар.

Установим такие учётные стоимости: 2 доллара за установку бита, 0 за очистку. При каждой установке бита одним из двух долларов учетной цены будем расплачиваться за реальные затраты на эту установку, а доллар, остающийся в резерве, будем прикреплять к установленному биту. Поскольку первоначально все биты были нулевыми, в каждый момент к каждому ненулевому биту будет прикреплен резервный доллар. Стало быть, за очистку любого бита ничего платить нам не придется: мы расплатимся за нее долларовой бумажкой, прикреплённой к этому биту в момент его установки.

Теперь легко определить учётную стоимость операции Increment: поскольку каждая такая операция требует не более одной установки бита, ее учётную стоимость можно считать равной 2 долларам. Следовательно, фактическая стоимость п последовательных операций Increment, начинающихся с нуля, есть О(п), поскольку она не превосходит суммы учётных стоимостей.

Упражнения

18.2-1 Предположим, что мы работаем со стеком, максимальный размер которого равен к, причем после каждых к операций делается резервная копия стека. Покажите, что суммарная стоимость п операций со стеком (включая резервное копирование) есть О(п), выбрав подходящие учётные стоимости.

18.2-2 Сделайте упражнение 18.1-3 с помощью метода предоплаты.


18.2-3 Добавим к системе операций с двоичным счётчиком операцию Reset (очистить все биты). Реализуйте счетчик на базе вектора битов таким образом, чтобы стоимость последовательности п операций Increment и Reset, примененных к счётчику, в котором первоначально находился нуль, была равна О(п), причём константа не должна зависесть от к - числа битов в счётчике. (Указание: храните номер старшего ненулевого бита).

18.3. Метод потенциалов

Метод потенциалов (potential method) является обобщением метода предоплаты: здесь резерв не распределяется между отдельными элементами структуры данных (например, отдельными битами двоичного счетчика), а является функцией состояния структуры данных в целом. Эта функция называется «потенциальной энергией», или «потенциалом».

Общая схема метода потенциалов такова. Пусть над структурой данных предстоит произвести п операций, и пусть Di - состояние структуры данных после г-й операции (в частности, Do - исходное состояние). Потенциал (potential) представляет собой функцию Ф из множества возможных состояний структуры данных во множество действительных чисел; эта функция называется ещё потенциальной функцией (potential function). Пусть сг- - реальная стоимость г-й операции. Учетной стоимостью (amortized cost) г-й операции объявим число

с,- = с,- + Ф(Д-)-Ф(Д- 1),(18.1)

т.е. сумму реальной стоимости операции плюс приращение потенциала в результате выполнения этой операции. Тогда суммарная учетная стоимость всех операций равна

пп

J> = с,- + Ф(£)п)-Ф(До).(18.2)

8 = 18 = 1

Если нам удалось придумать функцию Ф, для которой Ф( Ога) Ф(-Оо), то суммарная учетная стоимость даст верхнюю оценку для реальной стоимости последовательности п операций. Не ограничивая общности, можно считать, что Ф(-Оо) = 0 (см. упр. 18.3-1).

Говоря неформально, если разность потенциалов Ф(-Ог) - Ф( Ог-1) положительна, то учетная стоимость г-й операции включает в себя резерв («предоплату» за будущие операции); если же эта разность отрицательна, то учетная стоимость г-й операции меньше реальной, и разница покрывается за счет накопленного к этому моменту потенциала.



[стр.Начало] [стр.1] [стр.2] [стр.3] [стр.4] [стр.5] [стр.6] [стр.7] [стр.8] [стр.9] [стр.10] [стр.11] [стр.12] [стр.13] [стр.14] [стр.15] [стр.16] [стр.17] [стр.18] [стр.19] [стр.20] [стр.21] [стр.22] [стр.23] [стр.24] [стр.25] [стр.26] [стр.27] [стр.28] [стр.29] [стр.30] [стр.31] [стр.32] [стр.33] [стр.34] [стр.35] [стр.36] [стр.37] [стр.38] [стр.39] [стр.40] [стр.41] [стр.42] [стр.43] [стр.44] [стр.45] [стр.46] [стр.47] [стр.48] [стр.49] [стр.50] [стр.51] [стр.52] [стр.53] [стр.54] [стр.55] [стр.56] [стр.57] [стр.58] [стр.59] [стр.60] [стр.61] [стр.62] [стр.63] [стр.64] [стр.65] [стр.66] [стр.67] [стр.68] [стр.69] [стр.70] [стр.71] [стр.72] [стр.73] [стр.74] [стр.75] [стр.76] [стр.77] [стр.78] [стр.79] [стр.80] [стр.81] [стр.82] [стр.83] [стр.84] [стр.85] [стр.86] [стр.87] [стр.88] [стр.89] [стр.90] [стр.91] [стр.92] [стр.93] [стр.94] [стр.95] [стр.96] [стр.97] [стр.98] [стр.99] [стр.100] [стр.101] [стр.102] [стр.103] [стр.104] [стр.105] [стр.106] [стр.107] [стр.108] [стр.109] [стр.110] [стр.111] [стр.112] [стр.113] [стр.114] [стр.115] [стр.116] [стр.117] [стр.118] [стр.119] [стр.120] [стр.121] [стр.122] [стр.123] [стр.124] [стр.125] [стр.126] [стр.127] [стр.128] [стр.129] [стр.130] [стр.131] [стр.132] [стр.133] [стр.134] [стр.135] [стр.136] [стр.137] [стр.138] [стр.139] [стр.140] [стр.141] [стр.142] [стр.143] [стр.144] [стр.145] [стр.146] [стр.147] [стр.148] [стр.149] [стр.150] [стр.151] [стр.152] [стр.153] [стр.154] [стр.155] [стр.156] [стр.157] [стр.158] [стр.159] [стр.160] [стр.161] [стр.162] [стр.163] [стр.164] [стр.165] [стр.166] [стр.167] [стр.168] [стр.169] [стр.170] [стр.171] [стр.172] [стр.173] [стр.174] [стр.175] [стр.176] [стр.177] [стр.178] [стр.179] [стр.180] [стр.181] [стр.182] [стр.183] [стр.184] [стр.185] [стр.186] [стр.187] [стр.188] [стр.189] [стр.190] [стр.191] [стр.192] [стр.193] [стр.194] [стр.195] [стр.196] [стр.197] [стр.198] [стр.199] [стр.200] [стр.201] [стр.202] [стр.203] [стр.204] [стр.205] [стр.206] [стр.207] [стр.208] [стр.209] [стр.210] [стр.211] [стр.212] [стр.213] [стр.214] [стр.215] [стр.216] [стр.217] [стр.218] [стр.219] [стр.220] [стр.221] [стр.222] [стр.223] [стр.224] [стр.225] [стр.226] [стр.227] [стр.228] [стр.229] [стр.230] [стр.231] [стр.232] [стр.233] [стр.234] [стр.235] [стр.236] [стр.237] [стр.238] [стр.239] [стр.240] [стр.241] [стр.242] [стр.243] [стр.244] [стр.245] [стр.246] [стр.247] [стр.248] [стр.249] [стр.250] [стр.251] [стр.252] [стр.253] [стр.254] [стр.255] [стр.256] [стр.257] [стр.258] [стр.259] [стр.260] [стр.261] [стр.262] [стр.263] [стр.264] [стр.265] [стр.266] [стр.267] [стр.268] [стр.269] [стр.270] [стр.271] [стр.272] [стр.273] [стр.274] [стр.275] [стр.276] [стр.277] [стр.278] [стр.279] [стр.280] [стр.281] [стр.282] [стр.283] [стр.284] [стр.285] [стр.286] [стр.287] [стр.288] [стр.289] [стр.290] [стр.291] [стр.292] [стр.293] [стр.294]