計(jì)算機(jī)算法基礎(chǔ) 第2版 課件 第5章 中位數(shù)和任一順序數(shù)的選擇

1第5

章

中位數(shù)和任一順序數(shù)的選擇問題定義 2最大和最小數(shù)的選擇算法

4

同時(shí)找出最大數(shù)和最小數(shù)的算法

7線性時(shí)間找任一順序數(shù)的算法

10保證最壞情況復(fù)雜度是O(n)的算法

11平均情況復(fù)雜度為O(n)的算法

17找出k個(gè)最大順序數(shù)的算法

182

1.問題定義3

4找最大順序數(shù)算法如下：Maximum(A[1..n],max)max←A[1]fori←2

ton

ifmax<A[i]

thenmax←A[i]

endifendforreturnmaxEnd找最小數(shù)類似。這個(gè)算法需要(n-1)次比較。問題：能否用少於(n-1)次比較來找到最大數(shù)呢？2.最大和最小數(shù)的選擇算法

5定理5.1

任何基於比較的算法在n個(gè)不等的數(shù)字中找出最大順序數(shù)（或最小順序數(shù)）需要至少n-1次比較。證明：因?qū)ΨQ，我們只證最大數(shù)的情況。

我們把每次比較中較大的數(shù)稱為勝者，而較小的數(shù)為敗者。那么，數(shù)x

是最大順序數(shù)的充要條件是：它必須和某些其他的數(shù)比較過，并且每次都是勝者。其他的n-1個(gè)數(shù)都必須和某些數(shù)比較過并且至少有一次是敗者。如果每次比較后都在敗者上打一個(gè)印記，那么除了最大數(shù)，每個(gè)數(shù)都會被打上至少一次印記，總的印記數(shù)至少是n-1。因?yàn)槊看伪容^只打一個(gè)印記，所以比較次數(shù)至少是n-1。

類似地可證明，找最小順序數(shù)也需要至少n-1次比較。注意，這個(gè)下界是所有情況的下界，包括最好情況。6定理5.2

如果事先不知道輸入的n個(gè)數(shù)字中，任何兩個(gè)數(shù)字的大小關(guān)系，包括大于、小于、和相等，那么任何基于比較的算法在這n個(gè)數(shù)字中找出最大(或最小)數(shù)，至少需要n-1次比較。證明：

因?qū)ΨQ，只證最大數(shù)的情況。構(gòu)造圖G，初始只有n個(gè)頂點(diǎn)，代表這n個(gè)數(shù)。如果算法將數(shù)

a和數(shù)b作一次比較，則在代表

a和b的兩頂點(diǎn)之間畫一條邊。算法結(jié)束時(shí)，邊的個(gè)數(shù)就是比較次數(shù)?？勺C明G是連通圖。否則，必有連通子圖C，它和算法報(bào)告的最大數(shù)對應(yīng)的點(diǎn)無通路。我們可把C中每個(gè)數(shù)都加上同一個(gè)很大的數(shù)M，使最大

數(shù)不再是原來的數(shù)，而是C里的一個(gè)數(shù)。因?yàn)镃中點(diǎn)之間相對大小不會變，如果讓算法對更改后的n個(gè)數(shù)再找一次最大數(shù)的話，算法不會察覺更改，而仍會輸出相同的最大數(shù)。這就錯(cuò)了。因此，圖G必須是個(gè)連通圖。因?yàn)橛衝個(gè)頂點(diǎn)的連通圖必定含有至少n-1條邊，所以該算法至少用了n-1次比較，定理得證。

7如果分別找出最大和最小數(shù)，則需要2n-3次比較。同時(shí)把它們找出的步驟如下：(1)

順序把每兩個(gè)數(shù)字配為一組，即

A[1]和A[2]為第1組，A[3]和A[4]為第2組，…，

如果n是奇數(shù)，則最后一組只含一個(gè)數(shù)A[n]。(2)

比較A[1]和A[2]，大者放入變量max，而小者放入變量min(3) 從第2組開始，每組做3次比較：比較組內(nèi)兩個(gè)數(shù)決出誰大誰小。

(如只含A[n]，不需比較，A[n]既是大者又是小者。)大者和當(dāng)前max中的數(shù)比較以更新max小者和當(dāng)前min中的數(shù)比較以更新min。(偽碼見下頁)3.同時(shí)找出最大數(shù)和最小數(shù)的算法

8Maximum-minimum(A[1..n],max,min)ifn=1 thenmax←min←A[1]，exit，endifmin←min{A[1],A[2]}，max←max{A[1],A[2]} //第1組處理完ifn>2

then

fork←2

to

n/2

ifA[2k-1]<A[2k]

then

min←min{A[2k-1],min}

max←max{A[2k],max}

else

min←min{A[2k],min}

max←max{A[2k-1],max}

endif

endfor

if2k<n //n是奇數(shù)的情況

then

min←min{A[n],min}

max←max{A[n],max}

endif

endif

End9

10討論如何從n個(gè)數(shù)中找出第

i

順序數(shù)的問題

(1

i

n)。介紹兩個(gè)算法：(1) 保證最壞情況復(fù)雜度是O(n)的算法。(2) 平均情況復(fù)雜度是O(n)的算法。第一個(gè)算法的理論價(jià)值大于實(shí)際價(jià)值，因?yàn)樗粌H實(shí)現(xiàn)起來很復(fù)雜，而且時(shí)間O(n)中含有很大常數(shù)。4.線性時(shí)間找任一順序數(shù)的算法11保證最壞情況復(fù)雜度是O(n)的算法Select(setA,n,i) //1

i

n如果n

5，則排序后直接得到第

i順序數(shù)，分治法的底。每5個(gè)數(shù)為分一組，剩下不足5個(gè)的為一組。一共m=

n/5

組。找每組的中位數(shù)。m=

n/5

個(gè)中位數(shù)的集合記為M。遞歸調(diào)用Select(setM,m,

m/2

)

找出集合M的中位數(shù)x。把集合A的n

個(gè)數(shù)逐個(gè)與x比較后，劃分為三個(gè)子集如下： Set1={y

A|y<x} //所有小于x的數(shù)字 Set2={y

A|y=x} //所有等于x的數(shù)字，包含x本身 Set3={y

A|y>x}

//所有大于x的數(shù)字

設(shè)

|Set1|=a，|Set2|=b，|Set3|=c。(接下頁)12保證最壞情況復(fù)雜度是O(n)的算法

(繼續(xù))7 if

i

a

then

Select(Set1,a,i)

//集合A的第i

順序數(shù)也是Set1中第i順序數(shù)

else

if

a<i

a+b

//第i順序數(shù)存在于Set2

thenreturn

x

//Set2中任一個(gè)數(shù)都是第i順序數(shù)，包括x

else

k

i–(a+b)

Select(Set3,c,k)

//第i順序數(shù)是Set3中的第k順序數(shù) endifendifEnd13

14x至少有這么多數(shù)字小于等于x定理5.3 (證明繼續(xù)

1)我們借助下圖(5-1)來說明。

15

16

17平均情況復(fù)雜度為O(n)的算法用快排序中的劃分算法隨機(jī)地把集合A劃分為兩個(gè)集合。Quick-Select(A[p..r],m,i) //m=r–p+1Partition(A[p..r],q) //快排序中的劃分算法ifq–p

=

i

–1

//第一部分有i-1個(gè)數(shù)，A[q]是第i

順序數(shù)

then

returnA[q]

elseif

i<q–p+1

then

Quick-Select(A[p..q-1],q-p,i)

else

k

i–(q–p+1) Quick-Select(A[q+1..r],r-q,k)

//第i順序數(shù)是第二部分的第k順序數(shù)

endifendifEnd最壞情況下，算法需要O(n2)時(shí)間。平均情況的分析留為練習(xí)。18找出k個(gè)最大順序數(shù)的算法許多實(shí)際問題中，往住需要從n個(gè)數(shù)中找出k個(gè)最大的順序數(shù)。

例如，在眾多網(wǎng)站中，找出被訪問次數(shù)最多的100個(gè)網(wǎng)站。為方便，Select(setA,n,i)表示找第i大順序數(shù)，不是最小順序數(shù)。因?yàn)閷?shí)際問題中，n是有界的，需要理論聯(lián)系實(shí)際，根據(jù)n和k的關(guān)系以及n的大小來設(shè)計(jì)最佳算法。舉例：從十億個(gè)數(shù)字中找出一千個(gè)最大的數(shù)字。讓我們看幾個(gè)直觀的算法。重復(fù)找最大數(shù)的算法，大約需要kn

=1000n次比較。合并排序，大約需要nlgn

30n次比較，比算法(1)好。調(diào)用Select(setA,109,103)，找到第1000最大順序數(shù)x，然后再拿它和十億個(gè)數(shù)去比，大者留下。這樣做，不僅很繁，而且比較的次數(shù)大于30n。（見書中分析）19利用堆來找k個(gè)最大的順序數(shù)的算法算法1：k-Select(A[1..n],k)Build-Min-Heap(A[1..k],

1)for

i

(k+1)ton if

A[i]>A[1] //否則，跳過A[i],也就是丟棄A[i] then

A[1]

A[i] Min-Heapify(A[1..k],1) endifendforreturn

A[1..k]End思路是，堆中的k個(gè)數(shù)始終是目前檢查過的所有數(shù)中最大的k個(gè)數(shù)。這個(gè)方法最壞情況下大約需要2nlgk=20n次比較。20利用堆來找k個(gè)最大的順序數(shù)的算法(繼續(xù))算法2：用一個(gè)最大堆來對這n個(gè)數(shù)排序。不同的地方是，當(dāng)我們從堆中輸出k個(gè)最大數(shù)字后，排序中止。這個(gè)方法需要大約2n次比較建堆，而隨后輸出k個(gè)最大數(shù)需要最多2klgn

60,000<<n次比較。總共約2n次比較。這個(gè)方法的缺點(diǎn)是，當(dāng)n很大時(shí)，堆所占用的空間很大。利用錦標(biāo)賽樹來找k個(gè)最大順序數(shù)的算法錦標(biāo)賽樹是一個(gè)完全二叉樹，正好有n個(gè)葉子來存儲n個(gè)要排序的數(shù)字，并且所有葉子在底層或倒數(shù)第2層。下圖(5.2)給出一個(gè)有5個(gè)葉子的例子。

與堆相似，可用數(shù)組A[1..2n-1]來實(shí)現(xiàn)錦標(biāo)賽樹。(接下頁)21利用錦標(biāo)賽樹來找k個(gè)最大順序數(shù)的算法(繼續(xù)1)每個(gè)內(nèi)結(jié)點(diǎn)代表一次比較，當(dāng)它的兩個(gè)兒子處的比較有了結(jié)果之后，該結(jié)點(diǎn)處的比較即可進(jìn)行。每次比較中較大的數(shù)勝出。最后，在根結(jié)點(diǎn)的比較決出冠軍，得到最大數(shù)M。M被確定后，即可把它輸出，并把它所在的葉子中的值改為-

。重復(fù)上面的過程可得到下一個(gè)最大的數(shù)。因此，可用錦標(biāo)賽樹排序。例(圖5-2)：有5個(gè)葉子的一個(gè)錦標(biāo)賽樹。92471022利用錦標(biāo)賽樹來找k個(gè)最大順序數(shù)的算法(繼續(xù)2)因?yàn)橛?n-1)個(gè)內(nèi)結(jié)點(diǎn)，只需(n-1)次比較就可找到最大數(shù)。問題是，如果重復(fù)所有內(nèi)結(jié)點(diǎn)處的比較去