有n個操作序列，第i個操作如果i是2的精確冪，則花費2i，如果i是3的精確冪，則花費3i ，其他所有操作1。
嗨，首先我想說這是一個家庭作業問題，我不希望你爲我解決它。我已經使用聚合方法解決了它。爲此我總結了2的權力系列和3的權力系列，並得到了10的攤銷成本。然後我使用會計方法對它進行了檢查，對於很長的序列，它並沒有失敗。但我的問題是如何證明它永遠不會失敗，我可以按照我想要的那麼長的順序顯示，但它仍然不能保證它在一段時間後不會失效。
此外，我試着用潛在的函數方法解決它，這是我真的被卡住，設備潛在的功能，我認爲你需要真正的創造性，我無法找到一些條件，將永遠持有，也需要一些幫助。
只有一些關於如何在會計方法中證明它以及如何設置潛在函數的想法應該是足夠的。 謝謝
首先，忘記一分鐘「1爲所有其他操作」和「精確的力量3」位。如果當我是2的確切權力時，成本只是2i，會怎麼樣？那麼，假設我們假設每個操作的成本是4美元。也就是說，對於每一個操作，我們在我們的「IOU堆」中放入四個硬幣......然後當我們達到2的實際冪時，我們使用這些硬幣「支付」（這是描述潛在函數方法的一種方式）。
第1步：存入四個硬幣。需要支付2 * 1 = 2，所以我們的硬幣堆在兩個。
步驟2：再存入四枚硬幣。需要支付2 * 2 = 4，所以我們的堆又是兩個。
第3步：存入四個硬幣。樁現在有六個硬幣。
第4步：存入四個硬幣。樁現在有10個硬幣，但4是2的冪，所以是時候支付4 * 2 = 8，所以我們的樁再次下降到兩個硬幣。
步驟5-7：每個存入四個硬幣。總計現在是14個硬幣。
第8步：存入四枚硬幣（總數= 18），花費8 * 2 = 16，再次剩下兩枚硬幣。
要證明這裏的穩定狀態是我們一直在耗盡我們的硬幣到一個常數（2）是很容易的，但我們永遠不會低於。因此，攤銷成本是每次操作四個單位。
現在，假設當x是2的冪（否則爲零）時，運算X花費2i。假設當我是3的冪（否則爲零）時，操作Y花費3i。並且假設操作Z的費用爲1，除了當我是2的冪或3的冪時。觀察到你的問題相當於每次迭代執行操作X 和 Y 和 Z ......所以，如果你能弄清楚X，Y和Z的攤銷成本分開計算，您可以將這些成本相加以得到總攤銷成本。
我剛給你X;我將Y和Z作爲練習。 （儘管我不相信最終答案是10.接近10，也許......）
很好的答案......謝謝。 –