算法設(shè)計(jì)與分析9順序統(tǒng)計(jì)學(xué)

1、算法設(shè)計(jì)與分析2007.91第六章 順序統(tǒng)計(jì)學(xué)順序統(tǒng)計(jì)的概念線性期望時間選擇算法（過程及分析）最壞情況線性時間選擇算法（過程及分析）程序演示及說明26.1 順序統(tǒng)計(jì)的概念一、順序統(tǒng)計(jì)1、順序統(tǒng)計(jì)的概念：一個由n個元素組成的集合的第i個順序統(tǒng)計(jì)就是該集合中第i小的元素。例如，一個集合元素中的最小值即其第一個順序統(tǒng)計(jì)（i=1）；最大值即為其第n個順序統(tǒng)計(jì)（i=n）。 2、中位數(shù)的概念：一個中位數(shù)非正式的說即該集合的“中間點(diǎn)”上的元素。36.2 線性期望時間選擇算法一、選擇問題的定義 1、輸入：一個含n個（不同的）數(shù)的集合A和一個數(shù) i，1 in。 2、輸出：恰大于A中其他i-1個元素的xA。二、最

2、大最小元素的選擇算法 1、求n個元素集合中的最小元素 MINIMUM（A）1min A12for i 2 to length A3 do if minAi4 then minAi5return min 通過程序可以知道經(jīng)過n-1比較就可以確定最小值。46.2 線性期望時間選擇算法三、以線形期望時間做選擇 1、 RANDOMIZED-SELECT算法RANDOMIZED-SELECT（A,p,r,i）1 if p=r2 then return Ap3 q RANDOMIZED-PARTITION(A,p,r)4 k q-p+15 if i k6 then return RANDOMIZED-SE

3、LECT(A,p,q,i)7 else return RANDOMIZED-SELECT(A,q+1,r,i-k)56.2 線性期望時間選擇算法2、 RANDOMIZED-SELECT算法運(yùn)行時間分析a.最壞情況 RANDOMIZED-SELECT的最壞情況運(yùn)行時間為（n2）,即使是要選擇最小元素也是這樣，因?yàn)樵诿看蝿澐謺r可 能極不走運(yùn)，總是按所余下的元素中最大的進(jìn)行劃分。b.平均情況分析因?yàn)槭且粋€隨機(jī)化過程,所以沒有一個特別的輸入會導(dǎo)致最壞性態(tài)的發(fā)生，所以分析該算法的平均情況性能很有實(shí)際意義，通過分析我們會發(fā)現(xiàn)該算法的平均情況性能較好。66.2 線性期望時間選擇算法當(dāng)RANDOMIZED-S

4、ELECT作用于一個含n個元素的輸入數(shù)組上時，我們可以給出其期望時間的一個上界T(n)。在快速排序算法中我們曾經(jīng)分析過算法RANDOMIZED-PARTITION在產(chǎn)生劃分時，其低區(qū)中含1個元素的概率為2/n，含i個元素的概率是1/n，i=2,3,，n-1。假設(shè)T(n)是單調(diào)遞增的，在最壞情況下RANDOMIZED-SELECT的每次劃分中，第i個元素都在劃分的較大的一邊。這樣就得遞歸式：T（n） 76.2 線性期望時間選擇算法上面推導(dǎo)中由第一行到第二行是因?yàn)閙ax(1,n-1)=n-1，且 如果n是奇數(shù)，每一項(xiàng)T（n/2)， T（n/2+1) ，T（n/2+2)， T（n-1)在和式中個出現(xiàn)

5、了兩次;如果n是偶數(shù)，每一項(xiàng) T（n/2+1) ，T（n/2+2)， T（n-1) 個出現(xiàn)兩次， T（n/2) 只出現(xiàn)了一次。在各種情況中，第一行中的和式都由第二中的和式從上方限界。第二行到第三行是因?yàn)樵谧顗那闆r下T（n-1）=O(n2)，故1/nT(n-1)可被項(xiàng)O(n)吸收。86.2 線性期望時間選擇算法我們用歸納法解上面的遞歸式。假設(shè)對滿足遞歸式初始條件的某個常數(shù)c，有T(n) cn。將其代入我們剛才推導(dǎo)出來的式子：由這個歸納假設(shè)可得： 96.2 線性期望時間選擇算法 因?yàn)槲覀兛梢赃x擇足夠大的c使得c(n/4+1/2)能支配O(n)項(xiàng)。 總之，任意的順序統(tǒng)計(jì)（尤其是中位數(shù)）平均來說都可在

6、線性時間內(nèi)確定。106.3最壞情況線性時間選擇算法一、SELECT算法的基本步驟1、將輸入數(shù)組的n個元素劃分成n/5組，每組5個元素，且至多只有一個組包含余下的n mod 5個有元素 (如圖）。2、通過插入排序來找出每組中的中位數(shù)，并取其中間元素。（如果某組中有偶數(shù)個元素，則取兩個中位數(shù)中較大者。）3、對第二步中找出的n/5個中位數(shù)，遞歸調(diào)用SELECT以找出其中位數(shù)x。4、用修改的PARTITION版本、按x來對輸入數(shù)組進(jìn)行劃分。設(shè)k為劃分的低區(qū)中的元素?cái)?shù)，則(n-k)為高區(qū)中的元素?cái)?shù)。5、若ik，則在低區(qū)遞歸調(diào)用SELECT以找出第i小的元素；否則，若ik，則在高區(qū)找第（i-k)個最小元素

7、。116.3最壞情況線性時間選擇算法二、SELECT算法圖解 n個元素由小圓表示,每組占一個欄。各組的中數(shù)為白色，中數(shù)之中數(shù)x在圖中標(biāo)出。圖中所畫箭頭是由較大元素指向較小的元素，從中可以看出每組五個元素中在x右邊的三個大于x，在x左邊的三個小于x。所有大于x的元素以陰影背景襯出。126.3最壞情況線性時間選擇算法三、SELECT算法的運(yùn)行時間分析第2步找出的中位數(shù)中，至少有一半大于x，除了那個所含元素可能少5的組和包含x的那個組之外?？鄢@兩組，所有大于x的元素?cái)?shù)至少為：3（1/2 n/5-2）3n/10-6同理，小于x的元素至少有3n/10-6個。故在最壞情況下，第5步中至多有7n/10+6個元素遞歸調(diào)用SELECT?，F(xiàn)在就可以建立一個關(guān)于算法SELECT的最壞情況運(yùn)行時間T(n)的遞歸式。第1，2，和4步要花O(n)時間。（第2步對大小為O(1)的集合要調(diào)用O(n)次插入排序。）第3步需要時間T (n/5 ),第5步需時間至多為T（ 7n/10+6 ），若假設(shè)T是單調(diào)遞增的。請注意對n