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

創(chuàng)新互聯(lián)建站堅(jiān)持“要么做到，要么別承諾”的工作理念，服務(wù)領(lǐng)域包括：成都做網(wǎng)站、成都網(wǎng)站制作、企業(yè)官網(wǎng)、英文網(wǎng)站、手機(jī)端網(wǎng)站、網(wǎng)站推廣等服務(wù)，滿足客戶于互聯(lián)網(wǎng)時代的泊頭網(wǎng)站設(shè)計、移動媒體設(shè)計的需求，幫助企業(yè)找到有效的互聯(lián)網(wǎng)解決方案。努力成為您成熟可靠的網(wǎng)絡(luò)建設(shè)合作伙伴！

   題目是計算在鏈?zhǔn)焦１碇?，在均勻散列的情況下，命中查找的運(yùn)行時間。

   分析：命中查找的運(yùn)行時間，就是一個鍵數(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è)隨機(jī)變量X表示鍵a被插入到b鏈表后，后續(xù)插入的所有鍵被散列到b鏈表的個數(shù)。

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

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

有

X = ∑<i從1到n>(Zi ∑<k從i+1到n>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 + α)

                                                                                               ■

新聞標(biāo)題：鏈?zhǔn)焦Ｃ胁檎疫\(yùn)行時間數(shù)學(xué)證明-創(chuàng)新互聯(lián)
本文地址：http://jinyejixie.com/article34/cshcpe.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站設(shè)計公司、靜態(tài)網(wǎng)站、品牌網(wǎng)站制作、App設(shè)計、網(wǎng)站維護(hù)、自適應(yīng)網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)