動機
時不時看到，來搞懂他
做N次直接乘N?
以一般的雙loop，就是第一個loop乘上N就是N^2
因為裡面的loop都是N，但是如果不是每次都是N的話?
平攤分析
有些操作他有worst case與一般case，同時又會跑不特定多次，像online algorithm，如果要計算他操作的成本，只看worst case不太好，應該要算跑好幾次的平均成本
這就是平攤分析，簡單來說就是算平均
最簡單的做法是計算累積的成本，之後除總次數
像stack，一定是要先push，push是常數要N次，所以總成本就是N 就算mutil-pop(可以一次pop很多)的worst case是N，但是因為stack的總成本，能給mutil-pop的總成本是N，所以用平攤分析，mutil-pop是常數
還有其他分析法，但重點都是算 總成本 與 總次數
像是位能法的push的平攤成本為什麼是2? 因為做了這個操作才能，讓pop或是mutil-pop做事