Метод амортизированного анализа: учетные методы в алгоритмах и финансовой отчетности
Accounting method (computer science)
Метод амортизированного анализа в компьютерных науках: учет операций для оценки сложности алгоритмов. Интуитивный подход к определению стоимости операций.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Метод амортизационного анализа, методы бухгалтерского учета в бизнесе и финансовой отчетности
Method of amortized analysis
accounting methods in business and financial reporting
В области анализа алгоритмов в информатике метод бухгалтерского учета представляет собой метод амортизационного анализа, основанный на принципах бухгалтерского учета. Метод учета зачастую предоставляет более интуитивное представление об амортизированной стоимости операции, чем агрегированный анализ или метод потенциала. Однако следует отметить, что это не гарантирует очевидности такого анализа; часто выбор подходящих параметров для метода учета требует не меньшего понимания проблемы и границ сложности, которые необходимо доказать, чем при использовании двух других методов. Метод учета наиболее естественно подходит для доказательства временной сложности O(1). Описанный здесь метод предназначен именно для доказательства такой границы.
In the field of analysis of algorithms in computer science, the accounting method is a method of amortized analysis based on accounting. The accounting method often gives a more intuitive account of the amortized cost of an operation than either aggregate analysis or the potential method. Note, however, that this does not guarantee such analysis will be immediately obvious; often, choosing the correct parameters for the accounting method requires as much knowledge of the problem and the complexity bounds one is attempting to prove as the other two methods. The accounting method is most naturally suited for proving an O(1) bound on time. The method as explained here is for proving such a bound.
Метод
Выбирается набор элементарных операций, которые будут использоваться в алгоритме, и их стоимость произвольно устанавливается равной 1. Тот факт, что реальная стоимость этих операций может отличаться, не представляет собой принципиальной сложности. Важно, чтобы каждая элементарная операция имела постоянную стоимость. Каждой составной операции присваивается "плата". Плата предназначена для покрытия стоимости элементарных операций, необходимых для выполнения данной конкретной операции, при этом часть оставшейся платы помещается в резерв для последующего использования. Сложность задач, требующих амортизированного анализа, заключается в том, что некоторые операции в общем случае могут требовать затрат, превышающих постоянную величину. Это означает, что никакой фиксированной платы недостаточно для покрытия максимальной стоимости операции, рассматриваемой изолированно. Однако при правильном выборе платы это перестаёт быть проблемой: дорогостоящие операции будут выполняться только тогда, когда в резерве будет достаточно средств для покрытия их стоимости.
A set of elementary operations which will be used in the algorithm is chosen and their costs are arbitrarily set to 1. The fact that the costs of these operations may differ in reality presents no difficulty in principle. What is important is that each elementary operation has a constant cost. Each aggregate operation is assigned a "payment". The payment is intended to cover the cost of elementary operations needed to complete this particular operation, with some of the payment left over, placed in a pool to be used later. The difficulty with problems that require amortized analysis is that, in general, some of the operations will require greater than constant cost. This means that no constant payment will be enough to cover the worst case cost of an operation, in and of itself. With proper selection of payment, however, this is no longer a difficulty; the expensive operations will only occur when there is sufficient payment in the pool to cover their costs.
Примеры
Несколько примеров помогут проиллюстрировать применение метода бухгалтерского учета.
A few examples will help to illustrate the use of the accounting method.