會計法介紹

為每個操作類型分配一個平攤代價，保證在整個操作序列中平攤代價始終大于實際代價

設計思路：

需要結合數據結構的特點和算法的規律靈活設計

【棧操作】

問題定義：初始為空的棧進行push，pop，multipop操作的代價分析
設計思路：

由操作的代價規律 : push >= pop+multipop

則 2*push的代價 > 總代價

分析：

實際代價

平攤代價

設計的平攤代價滿足會計法的要求，則總代價O（2n），平攤代價O(2)

【二進制計數器】

問題定義：初始為0的k位二進制計數器代價分析
設計思路：

對于任何一個數位，0 ~> 1 的次數總大于等于 1~>0 的次數

分析：

設 0 ~>1的平攤代價為2，1~>0的平攤代價為0

設計的平攤代價滿足會計法的要求，則總代價O（2n），平攤代價O（2）

總結

以上是生活随笔為你收集整理的平摊分析--会计法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。