Python 攤銷分析
Python 攤銷分析
分期分析包括估算程序中操作序列的運行時間，而不考慮輸入值中數(shù)據(jù)分布的范圍。一個簡單的例子是在排序列表中查找值比在未排序列表中快。如果列表已經(jīng)排序，則數(shù)據(jù)分布的方式無關(guān)緊要。但是，當然，列表的長度會影響算法，因為它決定算法必須經(jīng)過的步驟才能獲得最終結(jié)果。
因此，我們看到，如果獲得排序列表的單個步驟的初始成本很高，則后續(xù)找到元素的步驟的成本變得相當?shù)?。因此，攤銷分析有助于我們找到一系列操作的最壞情況運行時間的限制。分攤分析有三種方法。
- 會計方法 - 這涉及為每個執(zhí)行的操作分配成本。 如果實際操作比指定的時間更快結(jié)束，那么分析中會積累一些積極的信用。在相反的情況下，它將是負信貸。為了跟蹤這些累計學分，我們使用堆?；驑湫螖?shù)據(jù)結(jié)構(gòu)。早期進行的操作（如清單分類）具有較高的攤銷成本，但隨著積累的信用被利用，較晚的操作具有較低的攤銷成本。所以攤余成本是實際成本的上限。
- 潛在方法 - 在這種方法中，將保??存的信用作為數(shù)據(jù)結(jié)構(gòu)狀態(tài)的數(shù)學函數(shù)用于將來的操作。 數(shù)學函數(shù)的評估和攤銷成本應(yīng)該是相等的。因此，當實際成本高于攤銷成本時，潛在價值會下降，并且將用于未來昂貴的運營。
- 綜合分析 - 在這種方法中，我們估計n步驟總成本的上限。 攤銷成本是總成本和步驟數(shù)（n）的簡單劃分。
相關(guān)文章
- Python break 語句
- Python 多線程
- Python 大O符號
- Python 算法理由
- Python3 教程
- Python3 環(huán)境搭建
- Python3 解釋器
- Python3 輸入和輸出
- Python choice() 函數(shù)
- Python File readline() 方法
- Python os.chmod() 方法
- Python os.chroot() 方法
- Python os.dup() 方法
- Python os.ftruncate() 方法
- Python os.mkdir() 方法
- Python capitalize()方法
- Python decode()方法
- Python rjust()方法
- Python zfill()方法
- Python 字典 Dictionary str()方法
Python基礎(chǔ)