鏈?zhǔn)焦Ｃ胁檎疫\(yùn)行時(shí)間數(shù)學(xué)證明-創(chuàng)新互聯(lián)

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

創(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)時(shí)代的泊頭網(wǎng)站設(shè)計(jì)、移動(dòng)媒體設(shè)計(jì)的需求，幫助企業(yè)找到有效的互聯(lián)網(wǎng)解決方案。努力成為您成熟可靠的網(wǎng)絡(luò)建設(shè)合作伙伴！

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

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

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

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

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

設(shè)隨機(jī)變量Zi表示第i次插入鍵時(shí)，選中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í)間數(shù)學(xué)證明-創(chuàng)新互聯(lián)
本文地址：http://muchs.cn/article34/cshcpe.html

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

廣告

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