在我看到的任何地方（在 SO 和其他來源上），攤銷分析通常僅適用于資料結構。例如對于動態陣列或展開樹。但是，我還沒有看到對純演算法進行攤銷分析的應用。說演算法的攤銷分析有意義嗎？攤銷分析假設了一系列操作，這對于資料結構是正確的，但對于演算法則不是。
uj5u.com熱心網友回復：
在許多字串演算法中，您使用攤銷來分析運行時間。例如，在線性時間內構建邊界陣列或后綴樹，或從后綴陣列遍歷模擬后綴樹。
后綴樹和后綴陣列當然是資料結構，但是您不會使用通常意義上的將一系列修改的成本相加的攤銷；您在構建它們或用于遍歷它們的演算法時使用它。您將有一些昂貴和一些便宜的步驟，并且攤銷可以更輕松地計算總運行時間。
通常，您在演算法中使用它，因為它可能依賴于資料，因此很難限制每個步驟中使用的時間，但是您可以通過各種攤銷引數限制總數。你在字串演算法中做了很多，我最熟悉的，但它到處都是。
當然，只有當您必須從某個明確定義的起點執行一系列操作時才有意義（因此您不會從昂貴的操作開始然后停止）。但是還有比修改資料結構更多的應用程式。
uj5u.com熱心網友回復：
如果存在某種允許在一個操作中完成的計算影響另一個操作中的計算性能的可變狀態，那么分攤一系列操作的成本才有意義。如果一系列操作的性能可以獨立分析為單個操作的性能總和，每個操作的性能不依賴于其他操作，則不進行攤銷。
所以從這個意義上說，攤銷分析只適用于資料結構，而不適用于純演算法。然而，這假設了“資料結構”的一個非常廣泛的定義，它實際上涵蓋了任何可變狀態。例如，這是一個值得商榷的區域變數是否協程，其持續而協同程式的執行暫停時，應該考慮的資料結構。
同樣，我們通常不會認為用LRU 快取裝飾的函式“是”一個資料結構，而是我們會說它“使用”快取的資料結構，并且在分析一系列呼叫的性能時（一些其中命中快取，其他未命中），我們不會說我們正在分析快取使用的資料結構，我們會說我們正在分析記憶演算法。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/321843.html
上一篇：使用構建插入和中值構建資料結構