В области анализа алгоритмов в информатике , то бухгалтерский учет метод представляет собой метод амортизационного анализа на основе учета . Метод бухгалтерского учета часто дает более интуитивный расчет амортизированной стоимости операции, чем агрегированный анализ или потенциальный метод . Обратите внимание, однако, что это не гарантирует, что такой анализ будет сразу очевиден; Часто выбор правильных параметров для метода бухгалтерского учета требует таких же глубоких знаний о проблеме и пределах сложности, которые один пытается доказать, как и два других метода.
Метод бухгалтерского учета наиболее естественно подходит для доказательства ограничения по времени O (1). Метод, описанный здесь, предназначен для доказательства такой оценки.
Метод
Выбирается набор элементарных операций, которые будут использоваться в алгоритме, и их стоимость произвольно устанавливается равной 1. Тот факт, что затраты на эти операции могут различаться в действительности, не представляет трудностей в принципе. Важно то, что каждая элементарная операция имеет постоянную стоимость.
Каждой агрегированной операции назначается «платеж». Платеж предназначен для покрытия затрат на элементарные операции, необходимые для выполнения этой конкретной операции, при этом часть оставшейся суммы платежа помещается в пул, который будет использоваться позже.
Сложность проблем, требующих амортизированного анализа, заключается в том, что, как правило, некоторые операции требуют затрат, превышающих постоянные. Это означает, что никакой постоянной оплаты не будет достаточно, чтобы покрыть расходы на операцию как таковую в самом худшем случае. Однако при правильном выборе платежа это больше не проблема; дорогостоящие операции будут происходить только тогда, когда в пуле будет достаточно платежей, чтобы покрыть их расходы.
Примеры
Несколько примеров помогут проиллюстрировать использование метода учета.
Расширение таблицы
Часто необходимо создать таблицу до того, как станет известно, сколько места необходимо. Одна из возможных стратегий - увеличить размер стола вдвое, когда он будет заполнен. Здесь мы будем использовать метод учета, чтобы показать, что амортизированная стоимость операции вставки в такую таблицу равна O (1).
Прежде чем подробно рассматривать процедуру, нам потребуются некоторые определения. Пусть Т быть таблицей, Й элемент для вставки, Num (Т) число элементов в Т , и размер (Т) выделенный размер Т . Мы предполагаем существование операций create_table (n), которые создают пустую таблицу размера n , которая на данный момент считается свободной, и elementary_insert (T, E), которая вставляет элемент E в таблицу T, для которой уже выделено пространство, с стоимость 1.
Следующий псевдокод иллюстрирует процедуру вставки таблицы:
функция table_insert (T, E), если num (T) = size (T) U: = create_table (2 × размер (T)) для каждого F в T elementary_insert (U, F) Т: = 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м. Пока записей, находящихся в данный момент в таблице, будет добавлено достаточно в пул, чтобы заплатить за создание новой таблицы, у нас все будет в порядке.
Мы не можем ожидать первого записи, чтобы помочь оплатить новый стол. Эти записи уже оплачены за текущий стол. Тогда мы должны полагаться на последний записи для оплаты стоимости . Это означает, что мы должны добавить к оплате за каждую запись, итого платежа 3 + 4 = 7.
Рекомендации
- Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест и Клиффорд Штайн . Введение в алгоритмы , второе издание. MIT Press и McGraw-Hill, 2001. ISBN 0-262-03293-7 . Раздел 17.2: Метод бухгалтерского учета, стр. 410–412.