Python 攤銷分析

分期分析包括估算程序中操作序列的運(yùn)行時(shí)間，而不考慮輸入值中數(shù)據(jù)分布的范圍。一個(gè)簡(jiǎn)單的例子是在排序列表中查找值比在未排序列表中快。如果列表已經(jīng)排序，則數(shù)據(jù)分布的方式無(wú)關(guān)緊要。但是，當(dāng)然，列表的長(zhǎng)度會(huì)影響算法，因?yàn)樗鼪Q定算法必須經(jīng)過(guò)的步驟才能獲得最終結(jié)果。

因此，我們看到，如果獲得排序列表的單個(gè)步驟的初始成本很高，則后續(xù)找到元素的步驟的成本變得相當(dāng)?shù)?。因此，攤銷分析有助于我們找到一系列操作的最壞情況運(yùn)行時(shí)間的限制。分?jǐn)偡治鲇腥N方法。

• 會(huì)計(jì)方法 - 這涉及為每個(gè)執(zhí)行的操作分配成本。 如果實(shí)際操作比指定的時(shí)間更快結(jié)束，那么分析中會(huì)積累一些積極的信用。在相反的情況下，它將是負(fù)信貸。為了跟蹤這些累計(jì)學(xué)分，我們使用堆?；驑湫螖?shù)據(jù)結(jié)構(gòu)。早期進(jìn)行的操作（如清單分類）具有較高的攤銷成本，但隨著積累的信用被利用，較晚的操作具有較低的攤銷成本。所以攤余成本是實(shí)際成本的上限。

• 潛在方法 - 在這種方法中，將保??存的信用作為數(shù)據(jù)結(jié)構(gòu)狀態(tài)的數(shù)學(xué)函數(shù)用于將來(lái)的操作。 數(shù)學(xué)函數(shù)的評(píng)估和攤銷成本應(yīng)該是相等的。因此，當(dāng)實(shí)際成本高于攤銷成本時(shí)，潛在價(jià)值會(huì)下降，并且將用于未來(lái)昂貴的運(yùn)營(yíng)。

• 綜合分析 - 在這種方法中，我們估計(jì)n步驟總成本的上限。 攤銷成本是總成本和步驟數(shù)（n）的簡(jiǎn)單劃分。