動態陣列 - Amortized Analysis ← 返回遊戲列表
Dynamic Array (容量: 1, 大小: 0)
0
總操作數
0
總成本
0.00
平攤成本
0
擴容次數
每次操作的實際成本
等待操作...

平攤分析 (Amortized Analysis)

動態陣列擴容策略:當陣列滿時,容量加倍。

單次 Push 成本
- 一般情況:O(1)(直接寫入)
- 擴容時:O(n)(複製所有元素)

平攤分析:n 次 push 的總成本 ≤ 3n
- 每個元素最多被複製 log(n) 次
- 平攤成本 = O(1)

三種分析方法:聚合分析、記帳法、勢能法