Account method

from Wikipedia, the free encyclopedia

The account method (or bank account paradigm or booking method) is a method of amortized runtime analysis . According to the account method, the real costs of individual operations of an algorithm are compared with amortized costs, and the difference is posted to an account.

Examples

Incrementing a binary counter

The account method is used to analyze the number of bit changes when a binary counter is incremented .

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 operations are set to one unit. In contrast, the amortized costs are set to 2 or 0 units. When a bit is set to 1, there are two units of amortized cost, only one of which is consumed and the remainder is deposited into the account. With the bit change from 1 to 0, one unit of amortized cost must be paid from the account.

Since exactly one bit is set from 0 to 1 with every increment of the counter, the account contains enough units to pay for all possible changes from 1 to 0. So are amortized total cost for incrementing in O .

Dynamic array

Dynamic arrays are often required in practice. One strategy to implement dynamic arrays is to double a static array whenever it is full. We want to use the so-called account method to show that the amortized cost of the inserts is O (1). We will find that if we enter the size n, we only have a running time of O (1). On average, we only have constant runtime because we do not enlarge the array with every insert operation, but only with every (n + 1) th insert operation. We have the (cheap) insert operations paid into an account so that the expensive operations, such as enlarging the table, can be paid for.

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 creates an empty array with size n (we take first to simplify the fact that this method has runtime = 0), elementary_insert(T, E), which stores an element E in an array T, with runtime of O (1).

We consider the following pseudocode : 

function table_insert(T,E)
    if num(T) = size(T)
        U := create_table(size(T) + 1)
        for each F in T
            elementary_insert(U,F)
        destroy_table(T)
        T := U
    elementary_insert(T,E)

Inserting n elements into the array T has a worst-case runtime of O (n 2 ) - this is due to the for-eachloop in line 4, which is run through every time table_insert is called and which causes num (T) elementary insert operations .

Is in line 3 

        U := create_table(size(T) × 2)

written, since the for-eachloop is run through much less frequently, the effort is O (3 × n − 3).

If we take a more differentiated look at the algorithm , then we can use the account method. For this, we set a deposit of three tokens (or time units) for each insert operation. This allows these cheap operations to pay for the expensive operations. You will see later why there have to be at least three tokens.

We assume that the table is initially empty and has size (T) = m. The first m insert operations therefore do not need to enlarge the table and have a running time of O (1). Each insert operation initially costs a token. This means that two tokens can effectively be deposited into the account for each insert operation.

If we insert the first m elements, the array is full and the following applies: num (T) = m. The account has (3 - 1) × m = 2m tokens. If we insert the (m + 1) th element, the array needs to be increased. The creation of a table should initially have a runtime of 0. The loop in line 4 takes n elementary inserts, which costs exactly m tokens. If you add the insert operation in the last row, the total cost of the operation is m + 1. After this operation, there are still 2m + 3 - (m + 1) = m + 2 tokens on the account. Now we add more m - 1 elements to the array. The account now has m + 2 + 2 × (m - 1) = 3m tokens. If we add another element (this is the (2m + 1) th element) then the operation incurs costs of 2m + 1 tokens and (like every insert operation) a deposit of three tokens. After this operation, the account will have 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 number of tokens for an insert operation must be at least three: A token is used directly for inserting the new element, a token is reserved in case the table is doubled and the inserted element has to be copied, and the last token is reserved for copying another element that was in the array before the last duplication of the array. (i.e. with size [T] = m, m / 2 elements for m elements pay the next copy action in advance, with a newly created array the third token is not used at all). Note : The tokens of an insert operation are assigned exactly to the next duplication.

We assumed that creating a new array had a running time of 0. In reality, building an array of size n can take O (n) in time. Would that change anything about our thinking? No, it turns out that we can use the same method to show that the amortized running time is again O (1). We just need to define the token deposit differently:

If a new 2m size array is created, there will be a current m size array. If the elements in the current array have deposited enough tokens into the account, there are no problems and we get a constant runtime again. How do we now have to define the token deposit? We can't expect the first few items to pay for the new table. These have already paid for the current array. So we have to make the final elements pay for it. So we have to add tokens to the payment for each insert operation so that each insert operation must now cost 3 + 4 = 7 tokens.

Steps in the amortized runtime analysis:

step Deposit to account Withdrawal from the account Balance after the operations
m insert elements 3m m 3m-m = 2m
Insert the (m + 1) th element 3 m + 1 2m + 3 - (m + 1) = m + 2
Add more m - 1 elements to the array 3 (m-1) m-1 m + 2 + 2 (m - 1) = 3m
Insert the (2m + 1) th element 3 2m + 1 3m + 3 - (2m + 1) = m + 2

Delete operations can be analyzed in the same way. E.g. a shrinking of the table would be just as useful if you want to save memory space. You would only need two tokens for each elemental erasure operation. This can easily be justified clearly: In the case of an enlargement, m / 2 elements must come up for the effort to copy m elements. When downsizing, each element only needs to have one token deposited into the account for copying.

See also

literature