Accounting method
The account method (or bank account paradigm or booking method ) is a method of amortized runtime analysis. After the account method the real cost of individual operations of an algorithm amortized cost are compared, and their difference is credited to an account.
Examples
Incrementing a binary counter
With the Account Method, the number of bit change is analyzed in the incrementing a binary counter.
Elementary operations are the setting of a bit from 0 to 1, or the setting of a bit from 1 to 0, the real costs for both operation can be set to one unit. In contrast, the amortized cost are set to 2 and 0 units. When a bit is set to 1, two units are formed amortized cost only one of which is consumed and the rest is deposited in the account. When the bit changes from 1 to 0 a unit amortized cost of the account must be paid.
Since exactly one bit is set from 0 to 1 at each incrementation of the counter, the account contains enough units to all possible change from 1 to 0 to pay. So the total cost amortized for incrementation are in O.
Dynamic array
In practice, often dynamic arrays are needed. A strategy to implement dynamic array is a static array always be doubled if it is full. We want to use the so-called accounts method to show that the amortized cost of insert operations is O ( 1). We will find that we n have only a term of O (1) for an input of size. So on average we only have a constant running time, because we do not enlarge the array at each insert operation, but only if each ( n 1) th insert operation. The ( cheap ) inserts we can deposit into an imaginary account so that the expensive operations, increasing table, can be paid.
Let T be an array, E be an element to be inserted. num (T ) is the current number of elements of T, and size ( T) is the current size of T. We assume that the following methods already exist: create_table ( n ), which applies a empty array of size n, ( we first assume for simplicity that this method duration = 0 has ) elementary_insert (T, E), which stores an element e in an array T. An insert operation causes a running time of O (1).
We consider the following pseudocode:
Table_insert function (T, E) if count ( t ) = size (T) U: = create_table (2 × size ( T)) for each F in T elementary_insert (U, F) T: = U elementary_insert (T, E) For the insertion of n elements in the array T is a worst-case results in running time of O (n2 ) - this is due to line 4, the num (T ) gives elementary inserts. Since we will consider the worst case assumed that the for-each loop is executed by table_insert at each call. If we want to consider the algorithm differentiated, then we can use the accounts method. To this end, we place a deposit of three tokens (or time units) determined for each insert operation. This can pay for the expensive operations of these favorable operations. Why does it have to be at least three tokens, we will see later.
We assume that the table is initially empty and size size (T ) = m has. Therefore, the first m insert operations do not increase the table and have a running time of O (1). Each insert will cost first time a token. That it can be paid into the account per insert operation effectively two tokens.
When we insert the first m elements, the array is full and we have: num (T ) = m. The account has ( 3 - 1 ) × m = 2m tokens. If we insert the (m 1) th element, the array must be enlarged. Creating a table is to first have a maturity of 0. The loop in line 4 takes n elementary inserts, what exactly m tokens costs. If we add the paste in the last line, the total cost of the surgery be m 1 After this operation, lying on the account or 2m 3 - (m 1 ) = m 2 tokens. Now we add another m - 1 elements in the array. The account now has m 2 2 × (m - 1 ) = 3m tokens. If we add another element (which is the (2m 1 ) th element ) then the operation cost more than 2m 1 tokens, and (like every insert operation ) a deposit of three tokens. After this operation, the account has 3M 3 - (2m 1 ) = m 2 tokens. Note: This is the same account balance as after inserting the (m 1) th element. We can show that this is always the case, no matter how many times the array is doubled.
We can now explain why the token number for an insert must be at least three: A token is consumed directly for the insertion of the new element, a token is reserved for the case that the table is doubled and the inserted element must be copied, and the last token is reserved for the copying of another element that was already present before the last doubling of the array in the array. (ie size [ T] = m, pay m / 2 elements of m elements the next copy action in advance, to a newly created array, the third token is not consumed). Note: The token insertion can be allocated accurately to the next doubling.
We have assumed that creating a new array has a duration of 0. In reality, you create an array of size n, a running time of O ( n ) have. Would that change anything in our consideration? No, it turns out that we can show by the same method that the amortized running time is O (1) again. We only need to define the token deposit different:
When a new array is created with size 2m, there is a current array of size m. If the elements in the current arrays have enough tokens paid into the account, there are no problems and we again obtain a constant term. How should we define the token deposit? We can not expect that the first elements of the new table pay. These have already paid for the current array. So we have to let the last elements pay for it. So we need to add tokens to the payment of each insert operation so that each insert operation now 3 4 = have to cost 7 tokens.
Steps in the amortized running time analysis:
Delete operations can be analyzed as well. For example. would be a reduction of the table just as useful if you want to save disk space. One would per unit erase operation even need only two tokens for this. Can be graphically justify this easy: With a magnification m / 2 elements for the effort m elements have to pay to copy. With a reduction of each element must have paid only a token for copying to the account.