計(jì)算機(jī)算法-設(shè)計(jì)與分析導(dǎo)論課后習(xí)題答案--資料

1、4.1 :在我們所了解的早期排序算法之中有一種叫做Maxsort的算法。它的工作流程如下：首先在未排序序列(初始時(shí)為整個(gè)序列)中選擇其中最大的元素max，然后將該元素同未排序序列中的最后一個(gè)元素交換。這時(shí)，max元素就包含在由每次的最大元素組成的已排序序列之中了，也就說這時(shí)的 max已經(jīng)不在未排序序列之中了。重復(fù)上述過程直到完成整個(gè)序列的 排序。(a) 寫出Maxsort算法。其中待排序序列為E，含有n個(gè)元素，腳標(biāo)為范圍為°川，n-1。void Maxsort(Element E) int maxID = 0;for (int i=Een gth; i>1; i-) for (

2、int j=0; j<i; j+) if (Ej > EmaxlD) maxID = k;Ei <-> EmaxID;(b) 說明在最壞情況下和平均情況下上述算法的比較次數(shù)。最壞情況同平均情況是相同的都是 C(n)=衛(wèi)口。y24.2：在以下的幾個(gè)練習(xí)中我們研究一種叫做“冒泡排序”的排序算法。該算法通過連續(xù) 幾遍瀏覽序列實(shí)現(xiàn)。排序策略是順序比較相鄰元素，如果這兩個(gè)元素未排序則交換這兩個(gè)元 素的位置。也就說，首先比較第一個(gè)元素和第二個(gè)元素，如果第一個(gè)元素大于第二個(gè)元素， 這交換這兩個(gè)元素的位置；然后比較第二個(gè)元素與第三個(gè)元素，按照需要交換兩個(gè)元素的位 置；以此類推。(a)起

3、泡排序的最壞情況為逆序輸入，比較次數(shù)為C(n)=血。(b)最好情況為已排z2序，需要(n-1)次比較。4.3:(a)歸納法：當(dāng)n=1時(shí)顯然成立，當(dāng)n=2時(shí)經(jīng)過一次起泡后，也顯然最大元素位于末尾；現(xiàn) 假設(shè)當(dāng)n=k-1是，命題也成立，則當(dāng)n=k時(shí)，對前k-1個(gè)元素經(jīng)過一次起泡后，根據(jù)假設(shè)顯 然第k-1個(gè)元素是前k-1個(gè)元素中最大的，現(xiàn)在根據(jù)起泡定義它要同第k個(gè)元素進(jìn)行比較，當(dāng)k元素大于k-1元素時(shí)，它為k個(gè)元素中最大的，命題成立；當(dāng) k元素小于k-1元素時(shí)， 它要同k-1交換，這時(shí)處于隊(duì)列末尾的顯然時(shí)隊(duì)列中最大的元素。綜上所述，當(dāng)n=k時(shí)命題成立。(b)反正法：假設(shè)當(dāng)沒有一對相鄰的元素需要交換位置

4、的時(shí)候，得到的序列是未排序的，則該未排序隊(duì)列至少存在一對元素是逆序的，現(xiàn)設(shè)這兩個(gè)元素未E(l)和E(i+k)，其中E(i)>E(i+k)。而根據(jù)沒有一對相鄰元素需要交換位置的條件，又有 E(i+k)>E(i+k-1)> >E(i+1)>E(i)，這是矛盾的。4.4：(a) 證明：根據(jù)4.3(a)j+1處交換后，j+1元素是前j+1個(gè)元素中最大的。又因?yàn)樵趈+1到 n-1之間沒有再發(fā)生交換，即說明 E(j+1)<E(j+2)<<E(n-2)<E(n-1)。綜上所述，從j+1位置 到n-1位置都已經(jīng)放置了最終排序結(jié)果的元素。(b)void bu

5、bbleSort(Element E, int n) int nu mPairs;int last;int j;last = n - 1;while(last>0) nu mPairs = last;last = -1;for(i nt j=0; j< nu mPairs; j+) if(Ej>Ej+1) In tercha nge Ej and Ej+1;last = j;return;(b) 這種改進(jìn)對最壞情況并沒有什么改進(jìn)，因?yàn)樵谧顗那闆r(倒序)時(shí)，還時(shí)從 n-1到1 的每個(gè)過程都循環(huán)一遍。4.5不可以。正如同前面練習(xí)中所說的那樣，已經(jīng)排序的并不一定在“正確的位置之上”

6、，這也許就是所說的“小局部，大局觀”吧。簡單的說明可以時(shí)，每一次向后的移動(dòng)都是針對當(dāng) 前最大值的，也就是說最大值的移動(dòng)是一移到底的，而同時(shí)相對小值的移動(dòng)每次最多是一步。所以說即使是局部已經(jīng)排序了，但是相對于“正確”排序的位置還是有差距的。4.61,n,n-1,2和n,n-1,3,1,2說明：將1放在n2的逆序中任何位置都不改變最壞情況。4.7插入排序的最佳情況是序列已排序，這時(shí)候需要比較次數(shù)為n-1次，移動(dòng)次數(shù)為0次。4.8(a) 最壞情況為插入位置在正數(shù)第2個(gè)位置，或者倒數(shù)第2個(gè)位置，比較次數(shù)i/2。在采用折半查找的時(shí)候，會(huì)設(shè)定已排序序列的首尾指針和當(dāng)前指針，這樣只有在第2個(gè)位置的元素進(jìn)行最

7、后的比較。(b) 在最壞情況下插入位置在第1個(gè)位置上，移動(dòng)次數(shù)為i次。(c) 由于折半插入排序只是減少了比較的次數(shù)，并沒有減少移動(dòng)的次數(shù)，所以算法的時(shí)間復(fù)雜度仍然是0( n2)的。(d) 采用鏈表數(shù)據(jù)結(jié)構(gòu)后的插入排序是可以減少元素的移動(dòng)次數(shù)的，因?yàn)檎麄€(gè)排序的最 多移動(dòng)次數(shù)為3(n-1)。但是這樣也僅僅是減少了元素的移動(dòng)時(shí)間，并沒有減少元素的比較次 數(shù)，所以算法的時(shí)間復(fù)制度仍然是 0(n2)的。4.9首先說明直接插入排序是穩(wěn)定的。在有重復(fù)鍵值輸入的情況下，插入排序的平均時(shí)間復(fù) 制度會(huì)有所增加，因?yàn)樵趯ふ也迦胛恢玫臅r(shí)候，會(huì)多比較那些相等的值。4.10含有n個(gè)元素的逆排序序列的逆序數(shù)為 W)。24.

8、11In tList listl nsSort(l ntList un sorted) In tList sorted,re mUn sort;sorted = n ull;remUn sort = un sorted;while (rem Un sort != n ull) int n ewE = first(rem Un sort);sorted = in sertl( newE,sorted);remUn sort = rest(rem Un sort);retur n sorted;算法分析：假設(shè)unsorted有n個(gè)元素。當(dāng)sorted已經(jīng)排序了 k個(gè)元素了，這時(shí)調(diào)用insertl

9、的時(shí)候，最好情況所耗時(shí)間為O(1) 的,平均情況和最壞情況的時(shí)間消耗為 O(k)的。調(diào)用insertl 時(shí)，變量k的變化范圍為0n-1的。因此在整個(gè)過程中的時(shí)間復(fù)制度，最好為 O(n)，平均和 最壞為0(n )4.124.13extendSmallRegion的后置條件為：在元素 Elow,.,EhighVac-1中最左面一個(gè)“樞紐” 的元素將被移動(dòng)到EhighVac中，并且指針會(huì)在這里返回；如果沒有這樣的元素，會(huì)將highVac 返回。4.15對于已經(jīng)排序的序列，進(jìn)行快速排序?qū)?huì)進(jìn)行n(衛(wèi)次比較和2(n1)次移動(dòng)。Efirst2被移動(dòng)到pivotElement，之后在每次調(diào)用一次partti

10、on的時(shí)候都被移動(dòng)到后面。4.17考慮含有k個(gè)元素的一個(gè)子區(qū)域。選擇“樞紐”需要 3( C：)次比較，對于其他k-3個(gè) 元素也需要進(jìn)行k-3次的同“樞紐”進(jìn)行比較，也就是說總共需要進(jìn)行 k次的比較。這相對 于簡單的選擇Efirst作為“樞紐”的方式并沒有多少改進(jìn)。一種極端的情況是在選擇 Efirst、 E(first+last)/2和Elast的時(shí)候，總是選中了兩個(gè)序列中最小的兩個(gè)元素，這樣每次都選中序2列中第二小的元素做“樞紐”的話，總的比較次數(shù)是-次。所以說對于逆序輸入的序列進(jìn)行4快速排序，如果采用選擇 Efirst、E(first+last)/2和Elast的中間元素作為“樞紐”的方法

11、的時(shí)間復(fù)制度仍然是0(n2)的。4.19(a) 在第一次調(diào)用后序列為：1, 9, 8, 7, 6, 5, 4, 3, 2，10；移動(dòng)1次。在第二次調(diào) 用后序列不變，沒有移動(dòng)。對含有 n個(gè)元素的逆序序列進(jìn)行排序，調(diào)用 partition的總的移動(dòng) 次數(shù)為-，同時(shí)還需要加上在選擇“樞紐”是用到的 2( n-1)次移動(dòng)。2(b) 在第一次調(diào)用后序列為：9, 8, 7, 6, 5, 4, 3, 2, 1, 10；移動(dòng) 18(2(n-1)次。 在第二次調(diào)用后序列為：8, 7, 6, 5, 4, 3, 2, 1, 9, 10；移動(dòng)16(2(n-2)次?？偟囊苿?dòng)n -1次數(shù)為2 i二n(n-1),另外還有在

12、選擇“樞紐”是用到的2(n-1)次移動(dòng)。(c) partitionL的最大優(yōu)點(diǎn)就是簡單。在多數(shù)情況下，調(diào)用 partitionL要比調(diào)用partition需 要更多的移動(dòng)次數(shù)。在 a和b中，partitionL需要做90 (10X 9)次移動(dòng)，而partition僅僅做 了 5 (10/2)次移動(dòng)。(另外完成快速排序還需要增加選擇“樞紐”是用到的 18次移動(dòng)。4.21(a)在partitionL中，只要“ unknown”元素小于“樞紐”元素，就會(huì)發(fā)生兩次移動(dòng)， 概率為】。所以對k個(gè)元素進(jìn)行排序的平均移動(dòng)次數(shù)為 墊 B。因此使用partitionL的快速2 2排序的移動(dòng)次數(shù)大約為1.4n lg

13、 n cn。(b) 在partition中，每個(gè) “unknown元素或者經(jīng)過extendSmallRegion檢測，或者經(jīng)過 extendLargeRegion檢測。在 extendSmallRegion 中，“ unknown元素在“大于等于”樞紐元素1的時(shí)候需要移動(dòng)，概率為 一；在extendLargeRegion中，“unknowri元素在“小于”樞紐兀素2的時(shí)候需要移動(dòng)，概率為一。所以平均的移動(dòng)次數(shù)為 坐 衛(wèi)。因此使用partition的快速排序2 2的移動(dòng)次數(shù)大約為0.7nlg n - cn(c) 使用partition的快速排序?qū)⑹褂?.4nlg n次比較和0.7nlg n次移動(dòng)

14、。歸并排序的時(shí)間 復(fù)制度大約是1.5nlg n。4.23IntList listMerge(IntList in 1,1 ntList in2) In tList merged;if (in1 = n il)merged = in2;else if (in2 = n il)merged = in1;else int e1 = first(i n1);int e2 = first(i n2);In tList remMerged;if (e1 <= e2) remMerged = listMerge(rest( in 1), i n2);merged = con s(e1, remMerg

15、ed);else remMerged = listMerge(i n1, rest( in 2);merged = con s(e2, remMerged);return merged;或者為：IntList listMerge(IntList in 1, IntList in2) returnin1 = nil ? in2 :in2 = nil ? in1 : first(in1) <= first(in2) ?cons(first(in1), listMerge(rest(in1), in2): cons(first(in2), listMerge(in1, rest(in2);4.

16、25方案1設(shè)P (k, m)為歸并排序k個(gè)元素的序列和m個(gè)元素的交換數(shù)，其中n = k + m。 則：If A0 < B0 then 調(diào)用 P(k-1，m)；If A0 > B0 then 調(diào)用 P(k, m-1)；n所以 P (k, m)= P (k-1, m) + P (k, m-1), Pkm)=。&丿方案2：在輸出序列中共有m+k個(gè)位置，如果第一個(gè)序列中的k個(gè)元素在輸出序列中 的位置已經(jīng)確定，則只需要將第二個(gè)序列中的 m個(gè)元素順序輸出到輸出序列中空缺的m個(gè)位置中就可以了。所以選擇這k個(gè)位置的輸出序列以二叉樹表示，分別需要的選擇方案為*m + k "*m +

17、 k、< 1 /< 2丿4.26'm + k如果輸入序列是已排序的，這合并兩個(gè)子序列需要n2次比較就可以了。遞歸表示為:nW(n) =W(-n是2的整數(shù)次幕，kW(n h n k2 -n-(,如果使得 k "gn，則 w( n)=nlgn y 2224.27(a)修改算法 Mergesort,增加一個(gè)工作序列的參數(shù)。在 Mergesort之上添加 mergeSortWrap,用于初始工作序列：mergeSortWrap(Eleme nt E, int first, int last) Eleme nt W = new Eleme ntEen gth; mergeS

18、ort(E, E, W , first, last);修改后的Mergesort為：mergeSort(Element in, Element out, Element work, int first, int last) if (first = last)if (in != out)outfirst = in first;else mid = (first + last) / 2;mergeSort(i n, work, out, first, mid);mergeSort(i n, work, out, mid + 1, last);雖然該算法需要三個(gè)序列參數(shù)，但是實(shí)際使用中僅有兩個(gè)E和W

19、。（b）由于輸入序列和輸出序列為不同的區(qū)域， 所以現(xiàn)在merge在每次比較的時(shí)候都需要 一次移動(dòng)。所以對于 mergesort來說，移動(dòng)次數(shù)將是n lg n。而對于快速排序，平均移動(dòng)次數(shù) 為 0.7 n lg n4.29對于深度為（D-1）的遞歸樹共有2dj個(gè)葉子結(jié)點(diǎn)，其中有（2D-1-B）個(gè)葉子可以有兩個(gè)孩 子，所以在深度為D的遞歸樹中有2（2D-B）個(gè)葉子。因此，n = 2（2D-B） B =2D -B，即 B =2D - n。4.311,2,02,1,00,2,10,1,24.34這不是大頂堆，因?yàn)?小于它的右孩子74.35“COMPLEXITY ”初始化為大頂堆后為“ YTXPOEMI

20、CL ”，比較次數(shù)為14 次(2+1+2+2+1+2+2+2)。4.37(a) 共需要9次；(b) 因?yàn)榇判蛐蛄幸呀?jīng)是降序的，所以在初始建堆時(shí)，每次調(diào)用FixHeap僅做一次或兩 次比較就可以了，并且不會(huì)有元素的移動(dòng)。因?yàn)槎呀Y(jié)構(gòu)所使用的二叉樹為“左完全二叉樹” ， 所以有如下已知條件：1、如果已知有n個(gè)結(jié)點(diǎn)，則該二叉樹有n-1條邊?，F(xiàn)分條件說明初始 建堆時(shí)的比較次數(shù)：1、如果n為偶數(shù)，則最后一個(gè)內(nèi)部結(jié)點(diǎn)只有一個(gè)左兒子，該結(jié)點(diǎn)僅需要一次比較；這時(shí) 有兩個(gè)孩子的結(jié)點(diǎn)個(gè)數(shù)為 丄三(根據(jù)已知條件1),這些結(jié)點(diǎn)需要兩次比較。所以總的比較次2數(shù)為 2* - 2 1 二 n -1 次。22、如果n為奇數(shù)，

21、則所有內(nèi)部結(jié)點(diǎn)都有兩個(gè)孩子，這些結(jié)點(diǎn)都需要兩次比較，則總的比較次數(shù)為2* n 1 =n -1次。2綜合1和2，當(dāng)n為正整數(shù)時(shí)，總的比較次數(shù)為 n-1次。(c) 對算法4.7 (初建堆)來說是最好的情況，因?yàn)橹恍枰猲-1次比較，沒有元素的移動(dòng)。4.40在推出for循環(huán)后，應(yīng)該附加條件E1E2(交換E1和E2)。這種改變僅僅是減少了在調(diào)用FixHeap時(shí)的過頂處理，并沒有減少比較次數(shù)。4.42( a)K = H100 = 1。將 100從 H1中移出；開始 fixHeapFast, vacant = 1 h = 6。比較 99, 98;將 99 移到 H1中；vacant 是 H2；比較 97,

22、96;將 97 移到 H2中；vacant 是 H4；比較 93, 92;將 93 移到 H4中；vacant 是 H8；比較K與H8的父結(jié)點(diǎn)，該結(jié)點(diǎn)為93。K 小,繼續(xù)，h = 3.比較 85, 84;將 85 移到 H8中；vacant 是 H16.比較 69, 68;將 69 移到 H16中；vacant 是 H32.比較K與H32的父結(jié)點(diǎn)，該結(jié)點(diǎn)為 69。K 小,繼續(xù)，h = 1.比較37, 36;然后將K同37比較；K 小,將37移到H32中，并將K插入到H64.(b) 4+ 3 + 2 = 9;(c) fixHeap做了 12次比較，除了葉子外每一層次比較了2次4.44證明:左邊=

23、lg(!h )+1 =|g( h+1+1 = |lg(2(h+2)如果h為奇數(shù)，這時(shí)2趴+2)1，所以左邊=lg(h - 1)=右邊；如果h為偶數(shù)，這時(shí)2典+1 2)=h 2，但是h+1為奇數(shù)，所以lg( h - 1)為非整數(shù)，所以lg(h 2) = lg(h 1)(說明：因?yàn)閔_1，且h為偶數(shù)，所以h的最小值為2，考慮函數(shù)y =lg(x 1)-lg(x) =lgn22組的時(shí)間約為k，k組總共的時(shí)間約為金，由于k為常數(shù)，所以片。崗。同樣道理,在其他階段所用的時(shí)間不會(huì)多于第一階段的時(shí)間，也就是不會(huì)超過0(n2)的量級，但是總的時(shí)間復(fù)制度仍然是0(n2)5.1畫出當(dāng)n為4時(shí)，算法FindMax （

24、算法1.3）的判定樹> <5.25.3我們以策論的觀點(diǎn)分析了查找 n個(gè)元素中最大元素和最小元素算法的下限。而如果 以判定樹的觀點(diǎn)我們會(huì)得到什么樣的下限呢？max = E1;sec on dLargest =-：;i = 1;while (i < n) if (E2*i = max) i = 2*i;if (Ei+1 > sec on dLargest) sec on dLargest = Ei+1;else i = 2*i+1;if (Ei-1 > sec on dLargest) sec on dLargest = Ei-1;retur n sec on dLa

25、rgest;5.5給出通過競爭的策略查找第二大元素的平均比較次數(shù)。a) 當(dāng)n為2的整數(shù)次幕。首先必須通過n-1次比較將最大元素排除，下面就是考慮相對于最大元素失敗的元素最 為候選的第二大元素的平均比較次數(shù)b) 當(dāng)n不是2的整數(shù)次幕。提示：參考練習(xí)5.4。5.6以下算法通過持續(xù)的掃描序列，并將最大的兩個(gè)元素保存下來的方法，查找含有n個(gè)元素的序列E的最大元素和第二大元素。(這里假設(shè)n 2)if (E1>E2)max = E1;sec ond = E2;elsemax = E2;sec ond = E1;for (i = 3; i<= n; i+)if (Ei > sec ond)

26、sec ond = max;max = Ei;elsesec ond = Ei;b) 給出在輸入為n時(shí)，該算法的平均比較次數(shù)。在每次循環(huán)中比較次數(shù)為一次或兩次，并且至少比較一次。只有在Ei為前i個(gè)元素中最大的兩個(gè)的時(shí)候會(huì)比較兩次，這時(shí)的概率為在進(jìn)行快速排序的時(shí)候，最壞情況為每次調(diào)用partition的時(shí)候只是分出一個(gè)元素來。如果輸入序列為已排序的，則使用findKth查找中間元素的調(diào)用為findKth (E,1 ,n,-')，這時(shí)會(huì) I遞歸的使用 w,川，2和sn來調(diào)用findKth。其內(nèi)部也會(huì)遞歸的使用該值調(diào)用在最壞情況下建堆需要2n次比較。如果在堆中含有m個(gè)元素，則使用 FixHe

27、ap的kDeleteMax大約需要2lg m次比較。因此，for循環(huán)大約需要進(jìn)行2(lg n-i)次比較。則總的5.15給出在最壞情況下僅比較7次就將5個(gè)元素的序列排序的算法。僅需要描述其步驟， 不需要寫出代碼。如同在圖5.2中那樣使用樹圖描述該步驟。提示：可以參考 5.6節(jié)中使用的 策略以減少比較次數(shù)。，而對于比較一次的概率為。另外，在ii進(jìn)入循環(huán)之前還比較了一次。所以平均比較次數(shù)為：n2 i 2門彳門門彳門1A(n) =1 八(2 -二)=1 4' ：' 1 _2 " n_2 2 -i z3i ii=3 ii=3i=3 i3 i:n -1 2(ln n -1) =

28、 n -3 2ln n5.8經(jīng)過修改的快速排序可以查找n個(gè)元素中第k大的元素，并且在大多數(shù)情況下這時(shí)所需要的時(shí)間要比完全排序n個(gè)元素的時(shí)間少。a) 為完成上述思想，實(shí)現(xiàn)修改后的快速算法findKth。該算法的核心思想是在遞歸的使用Quicksort時(shí)會(huì)將序列分成兩段，而對于findKth則僅僅需要對其中的某一段進(jìn)行查找就可以了。/* Precondition:first 蘭 k 蘭 last */Element findKth(Element E, int first, int last, int k)Eleme nt ans;if (first = last)ans = Efirst;els

29、eElement pivotElement = Efirst;Key pivot = pivotEleme nt.key;int splitPo int = partiti on(E, pivot, first, last);EsplitPo int = pivotEleme nt;if (k < splitPoi nt)ans = findKth(E, first, splitPoint - 1, k);else if (k > splitPoi nt)ans = fin dKth(E, splitPoi nt + 1, last, k);elseans = pivotEleme

30、 nt;return ans;b) 證明在使用findKth查找中間元素時(shí)，最壞情況為O(n2)。partition。根據(jù)對快速排序的分析，對這至少有 號個(gè)元素進(jìn)行快速排序，在最壞情況下的比較 次數(shù)為0(n2)的。所以，findKth在最壞情況下的比較次數(shù)也是 0(n2)的。c) 為計(jì)算該方法的平均運(yùn)行時(shí)間，列出其計(jì)算的遞歸方程。設(shè)有n個(gè)元素，要查找的元素序號為k，則該算法平均運(yùn)行時(shí)間的遞歸方程為：1 kJnJT(n,k)二 n -1 ' T(n -1i,k 一1 i) ' T(i 1,k) n 1, 0乞 k :：: nn7i土出丿T(1,0)=0該算法的運(yùn)行時(shí)間同比較次數(shù)近

31、似相同。為避免含有兩個(gè)參數(shù)的遞歸方程，我們可以通過一個(gè)上限表達(dá)式來替代確切的遞歸方程式。設(shè)T(n)為當(dāng)n個(gè)元素中k的位置為最壞情況式的平均比較次數(shù)，即為T(n)=maxT(n,k)，所以:1 fkn4、T(nn1+丄 2：T(n1i)十送 T(i -1)ni 土卅jd) 分析你的算法的平均運(yùn)行時(shí)間。給出漸進(jìn)估計(jì)。根據(jù)上述的遞歸方程，可以猜想T( n, k)_ cn，其中c為某一個(gè)確定的常數(shù)。為證明該假設(shè)，根據(jù)上述的簡化的遞歸方程有: 1( 1 1n -.IZ c(n 1i) + 5： c(i 1) =n-k(n1 + n k)c + ?(n 1 k)(k + n 2)c=n -1 c(n2 2

32、kn - 2k2 - 3n 2) 2n1 k31k1=n(1 ；c) k(c-c() c(-： ：) )-12 n2 2 nn為保證該不等式成立，并取得適當(dāng)?shù)某?shù)c,因?yàn)閗(c-cd)乞印，貝冋取c = 4。n 45.10假定使用如下算法查找n個(gè)元素中第k大的元素。Build a heap H out of the n keys;for (i=1; i<=k; i+)output(getMax(H);deleteMax(H);在k值取何值時(shí)，該算法的時(shí)間復(fù)雜度為線性的。比較次數(shù)的下界為2klg n，取k值為,則總的時(shí)間還是O(n)的lg n5.11給出查找n個(gè)元素中第k大元素的算法(1乞

33、k空n )。寫出所有影響運(yùn)行時(shí)間的執(zhí)行 細(xì)節(jié)，并給出該算法的時(shí)間復(fù)雜度描述，關(guān)于n和k的函數(shù)。5.12假設(shè)n為偶數(shù)，其中間元素為第n小的元素。對計(jì)算其平均時(shí)間復(fù)雜度的下限和定2理5.3 (其中假定n為奇數(shù))進(jìn)行必要的修改。無論n是奇數(shù)還是偶數(shù)都至少需要n-1次“必要的”比較。策略論的策略是利用表5.4中的定義，其中S狀態(tài)最多為-1，L狀態(tài)最多為-。根據(jù)表5.4中的定義，每一次比較最2 2多產(chǎn)生一個(gè)L狀態(tài)，也最多產(chǎn)生一個(gè)S狀態(tài)，而策略論的任何算法都可以至少剔除 -1次“非2必要的”比較。這時(shí)修改后的定理 5.3為：在n為偶數(shù)時(shí)，其中間元素為第-小的元素。任2何查找該中間元素的算法，在最壞情況下至

34、少需要凹-2次比較。25.14給出在最壞情況下，通過6次比較查找出5個(gè)元素中的中間元素的算法。僅需要描述其步驟，不需要寫出代碼。如同在圖5.2中那樣使用樹圖描述該步驟。提示：可以參考5.6節(jié)中使用的策略以減少比較次數(shù)。任何大于其它三個(gè)元素的元素或這時(shí)任何小于其他三個(gè)元素的元素都應(yīng)該被舍棄。為簡 化對該算法的描述，我們引入在練習(xí) 4.56中使用的CEX (比較-交換)指令。CEX i,j表示將 下標(biāo)為i和j的元素進(jìn)行比較，并在需要的時(shí)候進(jìn)行交換，以便使得值小的元素的下標(biāo)也是小 的。CEX 1,2 /比較1和2,將小值放在 1中，大值放在 2中；CEX 3,4 /比較3和4,將小值放在3中，大值放

35、在4中；CEX 1,3 /比較兩個(gè)較小的元素 1和3,將1, 2，3，4中最小的方在1中；這時(shí)可以斷定1中的元素/要比其他三個(gè)元素小，可以將其舍棄。而經(jīng)過比較后我們也知道了E(3) £ E(4)。CEX 2,5CEX 2,3 /經(jīng)過這兩次比較后，將剩余元素中最小的元素放在了2中；CEX 3,5 /經(jīng)過這次比較交換，將剩余元素中最小的元素放在了3中，而此元素也是所有 5個(gè)元素中/第三小的元素，也就是所求的中間元素。根據(jù)上題中的比較過程，經(jīng)過了 6次比較后確定了第一小元素在 E1 中，第二小的元素在E2中，第三小的元素在E3中，這時(shí)只要在增加一次比較 CEX 4,5，就會(huì)將第四小的元素放

36、在E4中，剩下的元素就是第五小的元素在E5中，這時(shí)也就是經(jīng)過了 7次比較將5個(gè)元素排序了。5.16以策論的觀點(diǎn)證明定理1.16 （在已排序序列中搜索的時(shí)間下限）提示：定義一個(gè)含 有待查找元素的有效序列段，段頭為該段的最小元素，段尾為該段的最大元素。定理1.16：任何通過比較方式在含有n個(gè)元素，且已排序的序列中搜索指定元素K的算法，都至少需要lg（n 1）次比較。假定序列E的下標(biāo)為0川I, n1，在其中搜索鍵值K。按照策論的策略保持一個(gè)包含鍵值K的子段，其變量含義及初始化定義如下：L。=0 （含有K的子段中的最小元素下標(biāo)，初始化為 0。）H。= n -1 （含有K的子段中的最大元素下標(biāo)，初始化為

37、 n-1。）M。 二口（含有K的子段的中間元素下標(biāo)，M = 也，初始化為 匸1 o）2 2 2R0 =n （含有K子段的元素?cái)?shù)目，初始化為n）在每次更改L和H后都必須對M和R進(jìn)行更新）假定我們進(jìn)行的是三路比較（二，>和 <）。按照下述步驟更新L和H :I、如果 i : Lq，則說明 K Ei ，更新 Lq = LqjHq = Hq；2、如果iHq，則說明K : Ei，更新Lq二Lq,Hq二Hq；3、如果LqJ Mq，則說明K Ei，更新Lq =i T,Hq二Hq；4、如果 Mqji 乞 Hq，則說明 K : Ei，更新 H1,LLqd）R + 1在上述步驟中，可以得到Rq 1 L例

38、如對步驟4 有:Hqj-LqjRq+1HqiTMqA-11Lqj§2 LqVRq1 二 Hq -Lq 22如果該算法在Rq =0之前停止，還是至少有兩種情況的輸出。例如，如果Lq = Hq，則Rq =1，這時(shí)或者是K =ELq，或者是K不在序列中?，F(xiàn)假定當(dāng)Rq =0時(shí)算法終止，根據(jù)上述遞歸式和初始條件Ro 1二n 1，可以得到(1、q_Rq十1 X I丄(n + 1)。因此有q Hlg( n +1)，又因?yàn)閝為整數(shù)則q 3lg(n+1)'。5.17已知序列E的索引為0|l,n (即E中包含n+1個(gè)元素)?，F(xiàn)假定E為單峰的，就說 存在某個(gè)索引值為M，對于小于索引M的元素是順序遞

39、增的，而對于大于索引 M的元素是 順序遞減的。這時(shí)EM為最大值元素。(注意，M可以是0或者n)現(xiàn)在的問題就是找到這 個(gè)M。a) 作為熱身動(dòng)作，說明當(dāng)n = 2時(shí)，兩次比較是必須的，并且是充分的。因?yàn)樵?個(gè)元素中找到其中最大值，通過兩次比較是必須的，而且是充分的。b) 寫出通過比較E中的元素來查找M的算法。算法策略為找到序列中第一個(gè)逆序，則該逆序的第一個(gè)元素即為M。void getM(Element E)for( int i=0; i<E.length-1; i+) if Ei<Ei+1 System.out.pri ntl n(Ei);return;System.out.pri n

40、tl n(EE.le ngth-1);return;c) 給出你的算法在最壞情況下的比較次數(shù)。(該算法應(yīng)該是O(n)的)上述算法在最后元素為所查找元素的時(shí)候?yàn)樽顗那闆r，比較次數(shù)為n次。d) 假定n= Fk，即為第k個(gè)斐波納契數(shù)，其中k2。給出經(jīng)過k-1次比較查找到M的 算法，僅需要描述算法的步驟就可以，不需要給出詳細(xì)的代碼。已知條件：Fk二卩心卡心，k_2 ;元素個(gè)數(shù)為Fk 1 ;e) 給出策論的基本策略，說明任何通過比較方式查找 M的算法至少需要lgn+2次比較，其中n 一4。這說明該問題僅僅比搜索已排序序列的問題稍微復(fù)雜一點(diǎn)。提示：細(xì)化5.16中的策略。5.18假設(shè)E1和E2都是含有n個(gè)元

41、素，并以升序排列的序列。a) 設(shè)計(jì)查找這2n個(gè)元素中第n小元素(該元素即為合并后集合的中間元素)的算法，限定該算法的復(fù)雜度為O(log n)。為簡單起見，可假設(shè)所有元素都是不等的。定理4.4任何通過比較將兩個(gè)都含有 n/2個(gè)元素的已排序序列合并為一個(gè)排序序列的算 法，在最壞情況下至少需要比較 n-1次比較。而在一個(gè)已排序序列中查找第k小的元素的時(shí)間為0(1)的。所以在先排序，再查找的策 略下解決該問題的時(shí)間為 0( n)的。b) 給出該問題的時(shí)間下界。5.19a) 給出判斷含有n個(gè)元素的序列中所有元素是否都是互不相同的算法。假設(shè)有三種比較 方式，也就是說比較兩個(gè)元素的結(jié)果可能是 、=或。說明該

42、算法共比較了多少次。將n個(gè)元素排序是L-)(n log n)的，并且在排序的時(shí)候在遇到有相等情況的時(shí)候會(huì)自動(dòng)的停 止排序或報(bào)告該信息。如果在排序的過程中沒有出現(xiàn)相等的情況，則說明該序列中所有的元 素都是互不相同的。(所有相鄰的元素在最后一次排序時(shí)都要直接進(jìn)行比較，否則算法不能確定序列已經(jīng)被排序了。)所以總的時(shí)間是P(nlog n)的。如果在使用排序算法的時(shí)候考慮到了相等的情況，則對已經(jīng)排序過的序列判斷其中是否 有相同的鍵，只需要掃描一遍就可以了，所用的時(shí)間也是0(n)的。所以總的時(shí)間還是0(n log n) 的。b) 給出所需比較次數(shù)的下限。(試一試C(nlog n)考慮序列中的所有元素都是互

43、不相同的。假定排序后元素為為：X2 ：山：:Xn。算法只有在獲取了相鄰元素X和XM的相對關(guān)系后，才具有用于排序的足夠信息。假定存在兩個(gè)元素X和Xi1，算法并沒有獲取關(guān)于它們的相對位置的信息。這時(shí)， 算法并 沒有足夠的信息確定Xi =x+，因?yàn)檫@些元素同序列中其他元素的比較不能提供這樣的信息。 這時(shí)，該算法聲明該序列中有兩個(gè)相等的元素的結(jié)論是錯(cuò)誤的。這時(shí)，如果該算法聲明該序 列中所有元素都是互不相同的，則只需要更改x，使其等于Xi 1，這時(shí)的更改對其他的比較結(jié)果是沒有影響的，所以算法給出了一個(gè)錯(cuò)誤的結(jié)論因此，為判斷序列中沒有相等的元素，算法也必須像排序那樣收集到足夠的信息才可以。這時(shí)看來雖然時(shí)間

44、下限都是 門51 og n）的，但是三路（=, 和）比較相對與兩路（ 和）對于解決該問題更加有效。但是如果序列中的所有元素都是互不相同的，則對于“的比較并不會(huì)提供任何有用的信息。所以在最壞情況下，對n個(gè)元素進(jìn)行排序還是需要-（nlog n）的,因此確定序列中是否有相同元素所需要的比較次數(shù)，在最壞情況下仍然是lUnlog n）的。5.20考慮判定長度為n的位串是否含有兩個(gè)連續(xù)0的子串的問題?；镜牟僮鞣绞绞菣z測位串的每一個(gè)位置，看該位置是 0還是1。對于n =2,3,4,5給出算法。boolean getTwo0( Bit E) count = 2;for (i=0; i<E.length

45、; i+) if (Ei=0)coun t-;elsecount = 2;if (co unt :=0) return ture;elsereturn false;5.21假設(shè)你的計(jì)算機(jī)內(nèi)存很小，并且還有一個(gè)包含順序鍵值元素的外部文件（或者在磁 盤上，或者在磁帶上）。鍵值可以被讀到內(nèi)存中處理，但是每一個(gè)鍵值只可讀一次。a）為查找該外部文件中鍵值最大的一個(gè)，最少需要多少的內(nèi)存存儲(chǔ)單元？給出證明。算法需要至少兩個(gè)存儲(chǔ)單元，一個(gè)用于存儲(chǔ)max，另一個(gè)用于存儲(chǔ)n ext。將讀入的第一個(gè)元素放入max中，然后每次都將下一個(gè)元素放入 next中，然后將其同max進(jìn)行比較，如 果next max，則將該元素

46、放入到 max中；否則讀取下一個(gè)元素。為解決該問題不可能再減 少存儲(chǔ)單元的數(shù)目了，如果僅使用一個(gè)存儲(chǔ)單元，那么連比較都進(jìn)行不了。b）如果是查找中間元素呢？為簡便起見可以假設(shè)n為奇數(shù)，這時(shí)中間元素為 丄，這時(shí)只需要 丄1個(gè)存儲(chǔ)空間就2 2可以解決該問題了。算法的策略是按照插入排序的方法，每次從外部文件中讀取一個(gè)元素， 并將其插入到前面已排序序列中，當(dāng)然對已排序序列只保存其前丄個(gè)元素，還需要一個(gè)存2儲(chǔ)單元用于存儲(chǔ)當(dāng)前讀入的鍵值，所以共需要 丄二1個(gè)存儲(chǔ)單元。2現(xiàn)在證明為解決該問題不可能再減少存儲(chǔ)空間的數(shù)目了，現(xiàn)假定存在某種算法，該算法使用更少的存儲(chǔ)空間來查找中間元素?，F(xiàn)在要說明的是這樣的算法會(huì)輸出

47、錯(cuò)誤的結(jié)果(對于- > 的問題，只要證明 > false就可以了。)在該算法選擇查找結(jié)果的時(shí)候，它會(huì)讀入某一個(gè)外部元素，并覆蓋掉以前讀入的某一個(gè)元素，可以將被覆蓋的元素稱作被排除 的元素，因?yàn)楦鶕?jù)問題中的條件它是不可能作為該算法的輸出了。這時(shí)，根據(jù)策論的方式， 我們可以使得該元素即為中間元素。假定第一個(gè)被覆蓋的元素為序列中第i小的元素，當(dāng)將其排除在外的時(shí)候，至少還有 匸5.22a) 已知有n個(gè)元素和某一整數(shù)k (iwkw n )。給出一個(gè)可以查找到任何一個(gè)第k小元素的高效算法。(例如，如果k=3，該算法可以給出第一小、第二小或第三小的元素。其中不 需要知道輸出元素的確切位置。)給出

48、該算法的比較次數(shù)。提示：不要試圖尋找復(fù)雜的方法。 給出一種短小，簡單的算法。在n個(gè)元素中查找到小于Ek的元素的算法需要n-k次比較。b) 給出解決該問題的比較次數(shù)的下限，是關(guān)于n和k的一個(gè)函數(shù)。為集合中的每一個(gè)元素分配一個(gè)權(quán)值 w(x)。 初始化所有鍵值，設(shè)置w(i)=1 ；2、 比較 Ei和 Ej，且 w(i) w(j)，Ei：Ej，則更新 w二 w(i) w( j), w( j) =0 ；3、比較 Ei和 Ej，且 w(i)=w(j) 0, Ei：Ej，則更新 w(iw(i) w(j),w(j0 ；4、比較 Ei和 Ej，且 w(i) : w(j)，Ei Ej，則更新 w(j)二w(i)

49、w(j),w(i) =0 ；5、比較Ei和Ej，且w二w(j) =0,則重復(fù)上述步驟，不進(jìn)行更新。經(jīng)過上述的步驟，只有權(quán)為 0的元素是在某次比較中獲勝的一方。由于在上述的步驟中 沒有為各個(gè)元素上的權(quán)加入新的值，所以總的權(quán)數(shù)為n。可以按照在證明定理5.2時(shí)那樣建立一個(gè)樹來分析這個(gè)過程。在比較的過程中，每一棵樹的根都是該樹中最小的元素，要合并兩 個(gè)樹，只需要比較它們的根元素，將失敗的元素作為新樹的根，然后將這兩棵樹分別作為它 的左右子樹。但是，無論何時(shí)，如果樹根為i，這w(i)的值代表了該樹中的節(jié)點(diǎn)數(shù)。 也就是說, 這個(gè)根元素將其他 w(i)-1個(gè)元素的權(quán)都贏了過來，在加上它自己本身的權(quán)值1,也就

50、是該樹的節(jié)點(diǎn)數(shù)。5.24設(shè)M為一個(gè)n 5的整數(shù)矩陣，其中每一行的元素是遞增的（從左至右），每一列的 元素是遞增的（從上至下）?？紤]這樣的一個(gè)問題，判定整數(shù) x在M中的位置，或者確定x 不在M中。以策論的觀點(diǎn)給出解決該問題的比較次數(shù)的下限。該算法允許以三種方式比較x和 Mij，比較結(jié)果為 X ： Mi j,x= Mij或x Mij。個(gè)元素還沒有同它比較，同時(shí)假定在這些剩余元素中還有2n 1-(i -1)個(gè)元素要比該被排除的元素小。則綜合所有比該元素小的元素個(gè)數(shù)為 (i -1) 口一(i 1)= 口 個(gè)，這時(shí)該被排除的元素即為中間元素。2 2這時(shí)，如果要查找小于K的元素，就需要在算法執(zhí)行到中間的某

51、一時(shí)刻停止。當(dāng)所有沒 有元素的權(quán)n-k時(shí)，如果在這時(shí)停止該算法，則任何的輸出結(jié)果都是不對的?？梢约僭O(shè)Ek 在某一棵樹上，而根據(jù)已知條件，沒有樹的節(jié)點(diǎn)超過n-k，也就說不能確定在其他樹上的節(jié)點(diǎn) 是否都小于節(jié)點(diǎn)Ek。因此，算法應(yīng)該在只有一個(gè)鍵的權(quán)為 n-k+1時(shí)，輸出剩余的元素即為所求。因?yàn)檫@時(shí)已 經(jīng)有n-k+1個(gè)節(jié)點(diǎn)已經(jīng)被提取出來了，也就是所求。而有 n-k+1個(gè)節(jié)點(diǎn)的樹，有n-k條邊，每 條邊是比較一次的結(jié)果，就是說解決該問題的比較次數(shù)下限為n-k。5.23設(shè)E為含有n個(gè)元素的正整數(shù)序列。E中的“大半元素”是在這含有n個(gè)元素的序 列中出現(xiàn)次數(shù)為n次以上的元素?！按蟀朐亍眴栴}就是如果存在這樣的

52、元素，則輸出該元素；2如果這樣的元素不存在，則輸出-1。解決該問題的操作僅為比較 E中的元素，并做適當(dāng)?shù)囊?動(dòng)和拷貝。給出解決該問題的一個(gè)算法。分析在最壞情況下該算法的時(shí)間和空間復(fù)雜度。（實(shí)現(xiàn)0（n2）的復(fù)雜度是簡單的，但是該問題有一個(gè)線性的解決方案。提示：使用在 5.3.2節(jié)中使用 的設(shè)置變量的技術(shù)。）為簡單起見，設(shè)n為偶數(shù)。設(shè)節(jié)點(diǎn)信息為（鍵值，相等數(shù)），將這n個(gè)元素兩兩比較，規(guī) 則如下：1、為每一個(gè)元素中的“相等數(shù)”初始化為 1；2、將最底層的n個(gè)元素兩兩比較，如果左右兒子的元素相等，則新建節(jié)點(diǎn)的“鍵值”為 左兒子，“相等數(shù)”為左右兒子“相等數(shù)”之和；否則，新節(jié)點(diǎn)的“鍵值”可以左右 兒子的

53、任意一個(gè)，這里假設(shè)為較大的那一個(gè)，“相等數(shù)”為1;同時(shí)，記錄“相等數(shù)” 最大的那個(gè)節(jié)點(diǎn)的信息。3、順序按層兩兩比較，處理方法同 2；4、這樣經(jīng)過n-1次比較后，就選出了這n個(gè)元素中的最大值，同時(shí)也得到了“相等數(shù)” 最大的那個(gè)節(jié)點(diǎn)的信息，設(shè)為 M;5、如果M.相等數(shù) =2，貝U以該節(jié)點(diǎn)的元素值同序列中的所有元素進(jìn)行相等比較，并記 錄相等計(jì)數(shù)，如果該計(jì)數(shù)大于n/2,則輸出該元素；否則，直接輸出-1。注意：解決該冋題的咼效算法為第四章的習(xí)題 4.58。如果算法設(shè)計(jì)和策論觀點(diǎn)足夠的好， 則該算法的比較次數(shù)同該算法的下限是相同的。6.1在需要擴(kuò)大序列時(shí)，所使用的策略是兩倍復(fù)制當(dāng)前序列?，F(xiàn)在要使用四倍來復(fù)

54、制當(dāng) 前序列，評估這種策略的時(shí)間和空間耗費(fèi)。假定在有向序列中插入第(n+1)個(gè)元素的時(shí)候，觸發(fā)了雙倍復(fù)制序列操作。設(shè)當(dāng)從舊序列中復(fù)制一個(gè)元素到新序列時(shí)的時(shí)間消耗為 t (在這里設(shè)定t為某一固定值)。則在將舊序列 復(fù)制到新序列的時(shí)候需要進(jìn)行 n次傳輸操作。而這次在前一次雙倍復(fù)制操作已經(jīng)進(jìn)行了 -次2傳輸，再前次是-，并以此類推。則總的時(shí)間消耗為T1亡2tn。如果使用四倍復(fù)制策略，4o2in n'近 14則總的時(shí)間消耗為nt,-t,-t|，即T八 昇nt o對于空間消耗，四倍復(fù)制策略會(huì)分配4 16y4'3所需求空間總量的四倍，而兩倍復(fù)制策略會(huì)分配所需求空間總量的兩倍。6.2為保存棧的空間，在被分配的存儲(chǔ)空間存在片斷的時(shí)候會(huì)進(jìn)行適當(dāng)?shù)氖湛s。這可以 作為對雙倍數(shù)組負(fù)責(zé)策略的補(bǔ)充。假設(shè)在棧大小超出已分配空間大小的時(shí)候，所使用的分配策略為雙倍復(fù)制。使用“已攤 銷成本”方式，評估以下收縮策略。每次操作是否消耗固定的“已攤銷成本”的時(shí)間a) 如果pop操作后棧元素?cái)?shù)少于 N時(shí)，收縮棧的大小為N。2 2在最壞情況下的時(shí)間復(fù)雜度為 門(n)的。假定棧大小為N0，當(dāng)前棧中已經(jīng)有n個(gè)元素(大 小為n =No -1 )o這時(shí)如果連續(xù)執(zhí)行兩次push操作就會(huì)觸發(fā)雙倍復(fù)制動(dòng)作，所需要的時(shí)間為 2t Not，棧大小變?yōu)?No?，F(xiàn)在如果再連續(xù)進(jìn)行兩次pop操作，棧中的元素個(gè)數(shù)