當前位置:網站首頁>攤還分析-學習筆記

攤還分析-學習筆記

2022-05-15 08:20:39一個逍遙怪

參考博客:

攤還分析/平攤分析(Amortized Analysis):從白癡到入門_那我就換個名字吧的博客-CSDN博客_攤還分析


攤還分析(1)——算法導論(23) - 學數學的程序猿 - 博客園


白話筆記:

三種方法:

        1、聚合分析

                算出整個過程的操作數總和,求平均(需要點數學計算)

        2、核算法

                對需要的操作進行“配對”,如操作A和操作B配對,執行操作A的時候就把操作B的費用支付了,執行操作B是不再支付。例如棧操作裏面的pop和push配對,二進制操作中的置1和置0配對。(需要找到配對關系)

        3、勢能法

        ​​​​​​​        取一個中間變化過程,根據“能量守恒”來做等式:

        ​​​​​​​        

                每個操作的攤還代價為其實際代價與其引起的勢能變化的和,總攤還代價為總實際代價的一個上界。(勢能計算方法需要自定義)

總的來說,第一種方法直接算就行了,數學公式計算就好了,第二第三中方法需要在思路上有一些轉換,算是一些小技巧吧。

(僅僅是學習筆記,可能有理解錯誤的地方,望批評指正。)


 

版權聲明
本文為[一個逍遙怪]所創,轉載請帶上原文鏈接,感謝
https://cht.chowdera.com/2022/135/202205142358441935.html

隨機推薦