會計方法(計算機科學)
在計算機科學算法分析的領域中,會計方法是一種基於會計分析的攤銷分析方法。會計方法通常比匯總分析或潛在方法更直觀地說明操作的攤銷成本。但是,請注意,這不能保證這種分析會立即顯而易見。通常,為會計方法選擇正確的參數需要對問題的知識,並且複雜性範圍是人們試圖與其他兩種方法一起證明。
會計方法最自然地適合於證明O (1)按時綁定。此處解釋的方法是為了證明這種約束。
方法
選擇將在算法中使用的一組基本操作,並將其成本任意設置為1。這些操作的成本在現實中可能有所不同。重要的是,每個基本操作都有恆定的成本。
每個匯總操作都被分配了“付款”。該付款旨在支付完成此特定操作所需的基本操作費用,其中一些付款剩下,將其放置在以後使用的池中。
需要攤銷分析的問題的困難在於,通常,某些操作將需要大於恆定成本。這意味著不持續的付款將足以支付其本身最糟糕的操作成本。但是,通過適當選擇付款,這不再是一個困難。昂貴的操作只有在池中有足夠的付款來支付其費用時才會發生。
例子
一些示例將有助於說明會計方法的使用。
表擴展
通常有必要在知道需要多少空間之前創建一個表。一種可能的策略是將桌子的大小加倍。在這裡,我們將使用會計方法表明該表中插入操作的攤銷成本為O (1)。
在詳細查看過程之前,我們需要一些定義。令t為一個表格, e插入的元素,num(t) t中的元素數量和大小(t) t的分配大小。我們假設存在create_table(n)的操作的存在,它創建了一個大小為n的空表,現在假定為免費,而elementary_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下次展開表時移動元素的付款表已擴展。直覺上,這解釋了為什麼元素的貢獻永遠不會“用完”,而不管桌子的擴展多少次:由於桌子總是翻了一番,最新的半部分總是涵蓋移動最古老的一半的成本。
我們最初認為創建表是免費的。實際上,創建尺寸N的表可能與O(n)一樣昂貴。讓我們說,創建尺寸n的表的成本是n。這個新費用會帶來困難嗎?並不真地;事實證明,我們使用相同的方法顯示攤銷的O(1)邊界。我們要做的就是更改付款。
創建新表格時,有一個帶有M條目的舊表。新表格為2m。只要當前表中的條目已在池中添加了足夠多的錢來為創建新表付費,我們就可以了。
我們不能指望第一個條目以幫助支付新桌子。這些條目已經為當前表付費。然後,我們必須依靠最後
支付費用的條目
。這意味著我們必須添加
要為每個條目的付款,總付款3 + 4 = 7。