具有線性級數的動態數組的分期複雜性？

假設一個數組最初是空的，其大小爲5，並且每次填滿所有插槽時數組擴大5。具有線性級數的動態數組的分期複雜性？

我明白，如果我們只考慮ň追加的任何序列（）操作，攤銷成本是O（N），因爲總成本將是：

5+(5+1＊5)+（5＋2＊5)＋...+(5＋(floor(n/5)-1)*5) = O(n^2).

*其中地板（ n/5）是陣列擴展的數量。

但是，如果它是n個操作的任何序列都包含pop（）？假設pop（）不會更改數組大小。

我的方式顯然不會工作，我已閱讀CLRS，但我仍然相當困難。任何幫助，將不勝感激。

2014-10-27 Pig

您似乎只在數組的末尾插入（因爲在公式中移動項目時沒有關聯的成本），所以僅在數組末尾使用刪除操作（「pop」）或者您是否想要在數組的任意點處進行刪除（在這種情況下，您需要移動物體）？ – 2014-10-27 08:01:44

指定的數量太少是一個合理的問題，需要回答：擴展N長度數組的成本是多少？你想在哪裏刪除？刪除時，「高」元素是否滑落，或者是否可以用最後一個元素插入孔？或者你可以讓元素「空」嗎？你需要維護的成本和語義不清楚。 – Kaganar 2014-10-27 15:08:43

@AnttiHuima對不起，他們應該像追加和流行。 – Pig 2014-10-27 16:03:10

答案有點令人失望，如果您的序列包含s許多推動或流行操作，那麼每項操作的攤銷成本爲O(s)。

要櫻桃挑線從另一個問題是非常好的answer：

平攤分析給出了每個操作的最壞情況下的平均表現（一段時間內）。

最壞的情況很明顯：反覆推送。在這種情況下，您的原始分析站立。

2014-10-27 17:37:42 Kaganar

感謝您的答案，但在最後一行中，這是否意味着最壞的情況不會彈出（）？ – Pig 2014-10-27 20:40:25

這將是正確的。 – Kaganar 2014-10-27 21:07:51

回答