關於攤銷分析？

Question

我已經閱讀了coreman的攤銷分析，但無法理解它的真實含義。 我通過互聯網，但無法理解。請問有人讓我明白。謝謝

Answer 1

攤銷分析背後的想法是基於經濟學攤銷的想法：你現在花更多的錢，以節省資金隨着時間的推移。例如：您花費額外的500美元購買更現代，更省油的發動機，隨着時間的推移，您可以通過節省燃油來攤銷這500美元。

攤銷分析的方式與大多數其他類型不同的地方在於，它只關注整個操作序列，而不是單個操作。例如，最壞情況分析會將插入到動態數組中，並說「如果數組已滿，您需要將整個數組複製到一個更大的數組中，因此插入的最壞情況步驟複雜性一個動態數組是Ο(n)「。

攤銷最壞情況分析會說，調整隻發生非常罕，和它實際上給你買了在Ο(1)做插入可預見的未來的可能性。所以，雖然單個插入的最壞情況是Ο(n)，但這種最壞情況只會在每Ω(n)次操作中出現Ο(1)次，這意味着調整陣列大小的成本會在陣列的整個生存期內分攤，因此整個分攤的最壞情況插入到動態數組中的情況步驟複雜度爲Ο(1)。