Метод бухгалтерского учета (информатика)

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

Метод бухгалтерского учета наиболее естественно подходит для доказательства привязки O (1) ко времени. Описываемый здесь метод предназначен для доказательства такой границы.

Метод

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

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

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

Примеры

Несколько примеров помогут проиллюстрировать использование метода бухгалтерского учета.

Расширение таблицы

Часто бывает необходимо создать таблицу до того, как станет известно, сколько места необходимо. Одна из возможных стратегий — удвоить размер таблицы, когда она заполнена. Здесь мы воспользуемся методом бухгалтерского учета, чтобы показать, что амортизированная стоимость операции вставки в такую таблицу равна O (1).

Прежде чем рассмотреть процедуру подробно, нам потребуются некоторые определения. Пусть T — таблица, E — количество элементов в T , а size(T) — выделенный размер T. элемент для вставки, num(T) — Мы предполагаем существование операций create_table(n), которая создает пустую таблицу размера n , которая на данный момент считается свободной, и элементарной_insert(T,E), которая вставляет элемент E в таблицу T , для которой уже выделено пространство, с стоимость 1.

Следующий псевдокод иллюстрирует процедуру вставки таблицы:

function table_insert(T, E)
    if num(T) = size(T)
        U := create_table(2 × size(T))
        for each F in T
            elementary_insert(U, F)
        T := U
    elementary_insert(T, E)

Без амортизированного анализа лучшая граница, которую мы можем показать для n операций вставки, равна O(n) — это связано с циклом в строке 4, который выполняет num(T) элементарных вставок.

Для анализа методом бухгалтерского учета каждой вставке таблицы присваиваем выплату 3. Хотя причина этого сейчас не ясна, она станет ясна в ходе анализа.

Предположим, что изначально таблица пуста с размером (T) = m. Таким образом, первые m вставок не требуют перераспределения и имеют стоимость только 1 (для элементарной вставки). Следовательно, когда num(T) = m, пул имеет (3 - 1)×m = 2m.

Вставка элемента m + 1 требует перераспределения таблицы. Создание новой таблицы в строке 3 бесплатно (на данный момент). Цикл в строке 4 требует m элементарных вставок, стоимость которых равна m. Включая вставку в последнюю строку, общая стоимость этой операции равна m + 1. Таким образом, после этой операции пул имеет 2m + 3 - (m + 1) = m + 2.

Далее добавляем в таблицу еще m — 1 элементов. На данный момент в пуле m + 2 + 2×(m - 1) = 3m. Можно видеть, что вставка дополнительного элемента (т.е. элемента 2m + 1) стоит 2m + 1, а оплата равна 3. После этой операции в пуле имеется 3m + 3 - (2m + 1) = m + 2. Примечание. что это та же сумма, что и после вставки элемента m + 1. Фактически мы можем показать, что так будет и при любом количестве перераспределений.

Теперь становится понятно, почему плата за вставку равна 3. 1 платит за первую вставку элемента, 1 платит за перемещение элемента при следующем расширении таблицы и 1 платит за перемещение более старого элемента в следующий раз. таблица расширена. Интуитивно это объясняет, почему вклад элемента никогда не «иссякает», независимо от того, сколько раз расширяется таблица: поскольку таблица всегда удваивается, самая новая половина всегда покрывает стоимость перемещения самой старой половины.

Мы изначально предполагали, что создание таблицы — бесплатно. В действительности создание таблицы размера n может стоить столько же, сколько O(n). Допустим, стоимость создания таблицы размера n равна n. Представляет ли эта новая стоимость трудности? Не совсем; оказывается, что мы используем тот же метод, чтобы показать амортизированные границы O(1). Нам остается только изменить оплату.

Когда создается новая таблица, существует старая таблица с m записями. Новый стол будет размером 2 метра. Пока записи, находящиеся в данный момент в таблице, добавили в пул достаточно средств, чтобы оплатить создание новой таблицы, с нами все будет в порядке.

Мы не можем ожидать первого ${\frac {m}{2}}$ записи, которые помогут оплатить новый стол. Эти записи уже оплачены за текущую таблицу. Тогда мы должны полагаться на последнее ${\frac {m}{2}}$ записи для оплаты стоимости $2m$ . Это означает, что мы должны добавить ${\frac {2m}{m/2}}=4$ к оплате за каждую запись, на общую сумму 3 + 4 = 7.

Ссылки

Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест и Клиффорд Стейн . Введение в алгоритмы , второе издание. MIT Press и McGraw-Hill, 2001. ISBN 0-262-03293-7 . Раздел 17.2: Метод бухгалтерского учета, стр. 410–412.