《算法導(dǎo)論》中關(guān)于鏈?zhǔn)焦Ｃ胁檎疫\行時間數(shù)學(xué)證明，一上來就給出公式?jīng)]看明白，在網(wǎng)上搜了一圈沒找到解答心中疑問的文字，于是寫下這篇。

公司主營業(yè)務(wù)：網(wǎng)站制作、網(wǎng)站設(shè)計、移動網(wǎng)站開發(fā)等業(yè)務(wù)。幫助企業(yè)客戶真正實現(xiàn)互聯(lián)網(wǎng)宣傳，提高企業(yè)的競爭能力。創(chuàng)新互聯(lián)是一支青春激揚、勤奮敬業(yè)、活力青春激揚、勤奮敬業(yè)、活力澎湃、和諧高效的團隊。公司秉承以“開放、自由、嚴(yán)謹(jǐn)、自律”為核心的企業(yè)文化，感謝他們對我們的高要求，感謝他們從不同領(lǐng)域給我們帶來的挑戰(zhàn)，讓我們激情的團隊有機會用頭腦與智慧不斷的給客戶帶來驚喜。創(chuàng)新互聯(lián)推出八步免費做網(wǎng)站回饋大家。

    題目是計算在鏈?zhǔn)焦１碇校诰鶆蛏⒘械那闆r下，命中查找的運行時間。

    分析：命中查找的運行時間，就是一個鍵數(shù)目n的函數(shù)，按照成本模型便是求命中查找的比較次數(shù)隨n增長的增長率，即比較次數(shù)為n的函數(shù)T(n)。

    設(shè)要查找鍵a，a被散列到b鏈表中。命中查找的比較次數(shù)為b鏈表中排在a前面的元素個數(shù)+1.于是題目被轉(zhuǎn)化為鍵a被插入到b鏈表后，后續(xù)插入的所有鍵被散列到b鏈表的個數(shù)+1。

設(shè)隨機變量X表示鍵a被插入到b鏈表后，后續(xù)插入的所有鍵被散列到b鏈表的個數(shù)。

設(shè)隨機變量Yi表示第i次插入鍵時，鍵被散列到b鏈表中的指示器隨機變量。（指示器隨機變量即當(dāng)事件發(fā)生時為1，不發(fā)生時為0.這里表示第i次插入鍵時，鍵被散列到b鏈表中為1，散列到其他鏈表中為0）

設(shè)隨機變量Zi表示第i次插入鍵時，選中a作為插入的鍵的指示器隨機變量。

有

X = ∑(Zi ∑Yk)        ①

E[Zi] = 1/n                                             ②

E[Yi] = 1/m                                            ③

由上3式得

E[X] = ............ 此處省略20行 ............ = (n-1)/(2m)

題目所求期望即為1 + (n-1)/(2m) = 1 + α/2 - α/(2n)

T(n) = θ(1 + α)    

                                                                                                ■