關(guān)鍵詞 均攤界分析

在這一章，我們會(huì)分析在第4章和第6章里介紹過(guò)的若干種高級(jí)數(shù)據(jù)結(jié)構(gòu)的運(yùn)行時(shí)間，比如伸展樹(shù)、平衡樹(shù)、隊(duì)列、堆等。

在這一章，我們會(huì)分析M個(gè)操作序列中的任意序列的最壞情形運(yùn)行時(shí)間，這跟之前的單個(gè)操作的最壞情形分析是不一樣的。

雖然AML樹(shù)的標(biāo)準(zhǔn)樹(shù)操作中的每個(gè)操作的最壞運(yùn)行時(shí)間為，但是實(shí)現(xiàn)AML樹(shù)有點(diǎn)復(fù)雜，不僅是因?yàn)橐紤]多種情形，而且是因?yàn)樾枰_地維護(hù)和更新樹(shù)的平衡信息。使用AVL樹(shù)的原因是因?yàn)樵诜瞧胶鈽?shù)上執(zhí)行個(gè)操作序列時(shí)，可能某個(gè)序列會(huì)花費(fèi)時(shí)間，這個(gè)代價(jià)很高。而且，非平衡樹(shù)的主要問(wèn)題是這種情形可能會(huì)重復(fù)出現(xiàn)。

伸展樹(shù)提供了一種令人滿意的替代方案。雖然伸展樹(shù)的每個(gè)操作仍需花費(fèi)時(shí)間，但是前述退化現(xiàn)象(執(zhí)行個(gè)操作序列時(shí)可能出現(xiàn)某個(gè)操作花費(fèi))不會(huì)在伸展樹(shù)中重復(fù)出現(xiàn)，而且可以證明在伸展樹(shù)中，從整體上看，M個(gè)操作中的任一序列花費(fèi)的最壞時(shí)間為。長(zhǎng)期運(yùn)行下來(lái)，伸展樹(shù)的每個(gè)操作花費(fèi)的時(shí)間為。這就是伸展樹(shù)的均攤時(shí)間上界。

均攤上界比最壞情形上界更弱，因?yàn)榫鶖偨绮皇菍?duì)任一單個(gè)操作都成立的。因?yàn)閱未尾僮鞑粷M足均攤界不重要，所以如果既能保留操作序列的上界和又能簡(jiǎn)化數(shù)據(jù)結(jié)構(gòu)的話，那么我們就愿意犧牲單次操作的上界。

均攤上界比等價(jià)的平均情形上界更強(qiáng)，比如二叉搜索樹(shù)的每個(gè)操作花費(fèi)的平均情形時(shí)間為，二叉搜索樹(shù)的M個(gè)序列花費(fèi)的時(shí)間為。

由于推導(dǎo)均攤界需要處理整個(gè)序列，而不只是一個(gè)，則均攤分析是有技巧的。

本章的主要內(nèi)容有：

• 分析二項(xiàng)式隊(duì)列的操作；
• 分析偏斜堆的操作；
• 介紹和分析Fibonacci堆；
• 分析伸展樹(shù)；