今天第一堂課沒有上到@@
第二堂開始上ch17 Amortized Analysis
http://mropengate.blogspot.tw/2015/06/algorithm-amortized-analysis.html
它是一個成本平均化的概念
例如有一台印表機每印500張就要換紙
第500張換紙的時間成本顯然要加進第1~499張的時間成本去均攤
那為何要用Amortized Analysis呢?
因為在某些特定的case下,
(例如像前述的印表機問題,久久才出現一次鉅額成本)
用Amortized Analysis比起best case或worst case的分析更準
沒有留言:
張貼留言