17.4-1
1) 根據(jù)書(shū)上第十一章的定理11.6或11.7知，如果裝填因子 α=1 ，不成功的探測(cè)次數(shù)將會(huì)是無(wú)窮大，因此嚴(yán)格小于 1。
2) 動(dòng)態(tài)開(kāi)發(fā)地址散列表的插入算法在 α≥0.75 時(shí)進(jìn)行擴(kuò)張， α≤0.25 時(shí)進(jìn)行收縮。證明略。
3) 這是因?yàn)閷⒌? m 個(gè)元素插入到一個(gè)滿的表要花費(fèi) O(m) 的代價(jià)。

17.4-2
證明略

17.4-3
刪除時(shí)不引起收縮時(shí)，在操作前后勢(shì)能值的改變是 2 或 -2，所以 c^i=ci+Φ(Di)?Φ(Di?1)≤1+2=3∈O(1) 。若引起收縮，則有

c^i=ci+Φ(Di)?Φ(Di?1)≤num[Ti]+1+|2num[Ti]?size[Ti]|?|2num[Ti?1]?size[Ti?1]|=1∈O(1)

總結(jié)

以上是生活随笔為你收集整理的CLRS 17.4动态表的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。