冒泡~今天看了MIT算法導(dǎo)論公開課之第13課 平攤分析、表的擴(kuò)增、勢能方法的課程 所以做了以下記錄。

平攤分析

定義：

用平攤的思想來分析一個(gè)操作序列，以證明每個(gè)操作的平均代價(jià)很小，盡管其中一個(gè)或幾個(gè)操作的代價(jià)比較大。

先舉哈希表來進(jìn)入這個(gè)平攤的分析的思想（也就是平攤分析中的聚集分析，具體的下面會(huì)描述）

1.哈希表多大才合適呢？

通常情況下，如果增大的話，查找的速度會(huì)更快，但是這樣需要的空間就大了會(huì)浪費(fèi)空間。

在這樣的情況，通常對于要存儲(chǔ)n個(gè)元素的哈希表的大小最好為Θ(n)。

但是如果不知道要存儲(chǔ)的元素?cái)?shù)量時(shí)，如何設(shè)定哈希表的大??？

這個(gè)時(shí)候就要使用動(dòng)態(tài)表的策略

（思想：vector擴(kuò)展容量的方式，空間滿時(shí)重新分配兩倍當(dāng)前大小的空間，并移動(dòng)元素，釋放舊的空間。）

當(dāng)哈希表已滿，再加入元素時(shí)（溢出），將哈希表擴(kuò)大：

1.分配一個(gè)更大的表。

2.將舊表中的元素拷貝至新表。

3.釋放舊表的空間。

（注意：這個(gè)時(shí)候哈希表的size是2的整數(shù)次冪）

舉個(gè)栗子：

復(fù)雜度分析：

在最壞情況下，一次插入運(yùn)算的代價(jià)為Θ(n)。

關(guān)于第i次插入操作的代價(jià)，當(dāng)i-1為2的冪時(shí)，代價(jià)為i，其他時(shí)候，代價(jià)為1。?

由上面的圖，讓我們看看平均的時(shí)間復(fù)雜度，每次基本插入操作為1，空間溢出時(shí)需要開一個(gè)更大一倍的空間，并復(fù)制當(dāng)前的元素過去，所以空間溢出時(shí)所需要的時(shí)間為2的i次方（i為第幾次溢出）

用到平均但并不涉及到概率學(xué)，主要想表示的是在最壞情況下的平均表現(xiàn)。

三種方法：

a.聚集分析

b.記賬分析

c.勢能分析

聚集分析也就是剛剛上面所提到的關(guān)于哈希表大小以及插入擴(kuò)展的分析。

所以接下來敘述記賬分析和勢能分析

記賬分析

！可以這樣通俗的解釋一下：

想象自己擔(dān)任了一個(gè)會(huì)計(jì)，對第i個(gè)操作收費(fèi)為ci，收益?zhèn)€虛構(gòu)的平攤代價(jià)每一步運(yùn)算需要花費(fèi)$1,未用到的余款就被存到銀行，用于償付以后的操作。

如：每次插入收費(fèi)為3，插入消耗1，剩下的2存入銀行為表翻倍時(shí)做準(zhǔn)備（也就是說剩下的用于后續(xù)可能發(fā)生的表的空間翻倍和拷貝元素），要始終保證銀行的金額為正

即提前平攤，總能支付擴(kuò)充表的費(fèi)用，這樣某一個(gè)高開銷的操作會(huì)被平攤掉

注意：存款不能為負(fù)的。

勢能分析

與記賬法不同，記賬對每一次操作做平攤的估計(jì)，比如例子中平攤代價(jià)為3，并將本次操作剩余量存儲(chǔ)在該次操作上。勢能法是:與整個(gè)操作序列相關(guān)的。對比記賬法，記賬法為記錄每一次流水，勢能則只記錄總的存款額。

參考資料：MIT算法導(dǎo)論公開課之第13課 平攤分析、表的擴(kuò)增、勢能方法 - rye_whiskey的博客 - CSDN博客MIT算法導(dǎo)論公開課之第13課 平攤分析、表的擴(kuò)增、勢能方法 - rye_whiskey的博客 - CSDN博客

finally~

今天是10.24 程序員節(jié)~大家節(jié)日快樂鴨！多長頭發(fā)不掉發(fā)！