計(jì)算機(jī)算法基礎(chǔ) 第2版 習(xí)題及答案 第3章

PAGE15第3章 基于比較的排序給出一例證明在最壞情況下，合并算法至少需要n1+n2-1次比較。解：作為一個(gè)例子，如果數(shù)組A[1..n1]和數(shù)組B[1..n2]中數(shù)滿足以下條件，那么合并算法需要n1+n2-1次比較:A[1]<A[2]<A[3]<…<A[n1-1]<B[1]<B[2]<B[3]<…<B[n2]<A[n1]。(a) 設(shè)計(jì)一個(gè)復(fù)雜度為O(nlgn)的算法以確定數(shù)組A[1..n]中的n個(gè)數(shù)是否有相同的數(shù)字。 (b) 設(shè)計(jì)一個(gè)復(fù)雜度為O(nlgn)的算法把數(shù)組A[1..n]中出現(xiàn)奇數(shù)次的數(shù)字挑選出來。解：這兩個(gè)問題可以用排序來解決。我們假定n2。(a)Repeated-Number(A[1..n])Heap-sort(A[1..n]) //用堆排序?qū)[1..n]進(jìn)行排序fori2ton ifA[i]=A[i-1] thenreturn“Yes,A[i]andA[i-1]areidentical.” //報(bào)告A[i]和A[i-1]相同 endifendforreturn“Norepeatednumbers.” //沒有重復(fù)的數(shù)字End因?yàn)樵撍惴ǖ拇蟛糠謺r(shí)間化在第一步的排序，所以算法復(fù)雜度為O(nlgn)。(b)Odd-occurrence(A[1..n])Heap-sort(A[1..n]) //用堆排序?qū)[1..n]進(jìn)行排序sA[1] //A[1]是第一個(gè)要檢查的數(shù)j0 //出現(xiàn)奇數(shù)次的數(shù)將被按序放入B[1..j]oddtruefori:=2ton ifs=A[i] then ifodd=true thenoddfalse elseoddtrue endif else ifodd=false //A[i]有一個(gè)不同的值 then oddtrue sA[i] else jj+1 //odd=true，記錄到B中 B[j]s sA[i] //odd仍然為true，未變 endif endifendforifodd=true //最后一輪中，s=A[n]，此時(shí)處理 then jj+1 B[j]s endifreturnB[1..j]End 因?yàn)樵撍惴ǖ拇蟛糠謺r(shí)間化在第一步的排序，其復(fù)雜度為O(nlgn)，而后面步驟所需時(shí)間為O(n)，所以算法復(fù)雜度為O(nlgn)。(a) 一棵高為h

的堆最少和最多能含有多少個(gè)結(jié)點(diǎn)(包括所有內(nèi)結(jié)點(diǎn)和葉結(jié)點(diǎn))？ (b) 證明一個(gè)含有n個(gè)數(shù)的堆的高為?lgn?。解

: (a) 當(dāng)一棵高為h

的堆是一棵滿二叉樹時(shí)含有最多的結(jié)點(diǎn)。此時(shí)的結(jié)點(diǎn)數(shù)是：Nmax(h)=1+2+22+23...+2h=2h+1–1。 當(dāng)一棵高為h

的堆的底層只含有一個(gè)葉結(jié)點(diǎn)時(shí)，它含有的結(jié)點(diǎn)數(shù)最少。此時(shí)的結(jié)點(diǎn)數(shù)是：Nmin(h)=Nmax(h-1)+1=2h。(b) 設(shè)一個(gè)含有n個(gè)數(shù)的堆的高為h。從上題(a)可知：Nmin(h)￡n￡Nmax(h)，即2h￡n￡2h+1–1，也就是2h￡n<2h+1。由此可得h￡lgn<h+1。所以有h=?lgn?。假設(shè)Heap-Delete(A[1..n],i)表示將A[i]這個(gè)數(shù)從數(shù)組A[1..n]構(gòu)成的堆中刪去，并使所余n-1個(gè)數(shù)形成一個(gè)堆的操作。用偽碼設(shè)計(jì)一個(gè)復(fù)雜度為O(lgn)的算法來實(shí)現(xiàn)Heap-Delete(A[1..n],i)(1in)。解：Heap-Delete(A[1..n],i) //1inkey←A[i]A[i]?A[n]n←n–1ifin //如果i=n+1，則已被刪去 then ifkey>A[i] then Max-Heapify(A[1..n],i) else key←A[i] Heap-Increase-Key(A[1..n],i,key) endifendifEnd假設(shè)Heap-Decrease-Key(A[1..n],i,key)表示在數(shù)組A[1..n]構(gòu)成的堆中把A[i]的值減少為key，并把A[1..n]修復(fù)為一個(gè)堆的操作。用偽碼設(shè)計(jì)一個(gè)復(fù)雜度為O(lgn)的算法來實(shí)現(xiàn)Heap-Decrease-Key(A[1..n],i，key)(1in)。解：Heap-Decrease-Key(A[1..n],i,key) //1inifkey>A[i] thenreturn“error,newkeyislargerthancurrentkey” //錯(cuò)誤，新值大于現(xiàn)有值endifA[i]?keyMax-Heapify(A[1..n],i)End給定一個(gè)排好序的數(shù)組A[1]≤A[2]≤…≤A[n]，第2章里例2.1中的二元搜索算法可以用一棵二元搜索樹來描述。樹中每個(gè)內(nèi)結(jié)點(diǎn)含有一個(gè)數(shù)組中的數(shù)。樹根里的數(shù)是算法進(jìn)行比較的第一個(gè)數(shù)，即A[mid]。如果x=A[mid]，則搜索成功并報(bào)告。否則，根據(jù)結(jié)果是x<A[mid]還是x>A[mid]，算法決定是遞歸搜索左半部分，還是遞歸搜索右半部分。因而這棵二元搜索樹的左右兩子樹可相應(yīng)地遞歸構(gòu)造。下圖給出了當(dāng)n=1，2，3，4時(shí)二元搜索樹的例子。其中葉結(jié)點(diǎn)表示搜索失敗的情況。證明一棵二元搜索樹T的葉結(jié)點(diǎn)只出現(xiàn)在最底下二層。證明一棵含n個(gè)數(shù)的二元搜索樹的高度為h=élg(n+1)ù。解: (a)證明一棵二元搜索樹T的葉結(jié)點(diǎn)只出現(xiàn)在最底二層。我們對n進(jìn)行數(shù)學(xué)歸納。歸納基礎(chǔ)：當(dāng)n￡4，上面圖例直接證明了這個(gè)結(jié)論。歸納步驟： 假設(shè)當(dāng)n=1，2，…，k-1(k>4)時(shí)，一棵含n個(gè)內(nèi)結(jié)點(diǎn)的二元搜索樹T的葉結(jié)點(diǎn)只出現(xiàn)在最底二層。下面我們證明當(dāng)n=k時(shí)結(jié)論仍正確。我們分兩種情況證明。n是奇數(shù)。在這種情況下，左右兩子樹L和R都含有(n-1)/2個(gè)內(nèi)結(jié)點(diǎn)因而形狀完全相同。由歸納假設(shè)，它們的葉結(jié)點(diǎn)只出現(xiàn)在最底二層。這些葉結(jié)點(diǎn)也就是T的葉結(jié)點(diǎn)。所以結(jié)論正確。n是偶數(shù)。在這種情況下，左子樹含(n-2)/2=n/2-1個(gè)數(shù)字而右子樹含n/2個(gè)數(shù)字。因?yàn)樽笥易訕涠际峭耆鏄?，所以左子樹總共含?n-1)個(gè)結(jié)點(diǎn)而右子樹含(n+1)個(gè)結(jié)點(diǎn)(包括葉結(jié)點(diǎn))。右子樹正好比左子樹多二個(gè)結(jié)點(diǎn)。如果左右兩子樹L和R的高度相等，那么結(jié)論得證。故假定他們高度不等。如下圖所示，右子樹比左子樹必定高一層。因?yàn)橛易訕涞牡讓又辽俸€(gè)葉子，左子樹必須是一個(gè)滿二叉樹，否則它會(huì)比右子樹少至少3個(gè)結(jié)點(diǎn)，不可能。所以左子樹的所有葉子必須在最底層。這就是說，左右子樹的所有葉子都在最底二層。歸納成功。LLRh1h2h1-1證明一棵含n個(gè)數(shù)的二元搜索樹的高度為h=élog(n+1)ù。證明： 因?yàn)橐豢煤琻個(gè)數(shù)的二元搜索樹有(n+1)個(gè)葉子，它總共有2n+1個(gè)結(jié)點(diǎn)。假設(shè)它的高度為h。由(a)部分的解知，它的所有葉子在最底二層。因?yàn)榈讓又辽儆袃蓚€(gè)葉子，但不會(huì)多于2h個(gè)葉子，所以有(1+2+…+2h-1)+2￡2n+1￡1+2+…+2h-1+2h，即2h+1￡2n+1￡2h+1–1，即(2h+2)￡2n+2￡2h+1。由此得 2h-1+1￡(n+1)￡2h，2h-1<(n+1)￡2hh-1<log(n+1)￡hh-1<élog(n+1)ù￡h。所以有h=élog(n+1)ù。*一個(gè)結(jié)點(diǎn)在一棵樹中的高度就是以這個(gè)結(jié)點(diǎn)為根的子樹的高度。證明在一個(gè)有n個(gè)數(shù)字的堆中，高度為h的結(jié)點(diǎn)數(shù)最多為én2h+1ù證明: 設(shè)x是一個(gè)有n個(gè)數(shù)字的堆中高度為h的結(jié)點(diǎn)數(shù)。我們注意到兩棵高為h的子樹的結(jié)點(diǎn)不相交，即一棵高為h的子樹中結(jié)點(diǎn)不屬于任一個(gè)其他的高為h的子樹。另外，因?yàn)樗腥~結(jié)點(diǎn)都在最底兩層，所有高為h的子樹，最多除一個(gè)外，都必定是滿二叉樹。下面的圖清楚地解釋了這一點(diǎn)。唯一可能不是滿二叉樹的子樹唯一可能不是滿二叉樹的子樹一棵高為h的滿二叉樹一共有2h+1-1個(gè)結(jié)點(diǎn)。而一棵不是滿二叉樹的高為h的子樹，也至少有2h個(gè)結(jié)點(diǎn)?，F(xiàn)在，試想把這x個(gè)子樹中除了根以外的結(jié)點(diǎn)從T中刪除，剩下的部分是一個(gè)有x個(gè)葉子的完全二叉樹。這個(gè)樹中除葉子外的內(nèi)結(jié)點(diǎn)數(shù)正好是(x-1)個(gè)。他們正好是T中除高為h的子樹以外的結(jié)點(diǎn)集合。所以我們可得以下不等式：n≥(x-1)+(x-1)(2h+1-1)+2h=(x-1)(2h+1)+2h=x(2h+1)-2h+1+2h≥x(2h+1)-2h因此有x≤(n+2h)/(2h+1)=(n/2h+1)+1/2≤én2h+1ù+因?yàn)閤必須是整數(shù)，故有x≤én2h+1(K路合并問題) 利用最小堆(min-heap)設(shè)計(jì)一個(gè)時(shí)間復(fù)雜度為O(nlgk)的算法將k個(gè)排好序的序列合并為單一排好序的序列。這里n是所有k個(gè)序列中數(shù)字的總數(shù)。解: 假定A1，A2，...，Ak為k個(gè)要合并的序列。假設(shè)每個(gè)序列已從小到大排好，算法思路如下：首先，把每個(gè)序列的頭，A1[1],A2[1],...,Ak[1]，即各序列中最小的數(shù)取出并組織為一個(gè)最小堆。那么，堆中的根顯然是所有n個(gè)數(shù)中最小的數(shù)。 然后，每次將堆的根中的數(shù)取出并放到輸出序列中。根中的數(shù)必定是還未輸出的所有數(shù)中最小的數(shù)。如果根中的數(shù)來自序列Aj(1￡j￡k)，那么將根中的數(shù)輸出之后，我們把Aj中下一個(gè)最小的數(shù)，即當(dāng)前Aj的頭從序列Aj取走放到堆的根結(jié)點(diǎn)并將堆修復(fù)。如果序列Aj中沒有數(shù)字了，那么我們把堆的規(guī)模減一并修復(fù)。這時(shí)參加合并的序列少了一個(gè)。因?yàn)槎延筛餍蛄兄凶钚〉臄?shù)組成，在根中的數(shù)顯然是當(dāng)前還未輸出的所有數(shù)中最小的數(shù)，算法顯然正確。下面是這個(gè)算法的偽碼。我們假定初始時(shí)，每個(gè)序列至少有一個(gè)數(shù)字并用一個(gè)特殊記號(hào)￥表示序列結(jié)束。k-Merge(A1,A2,...,Ak)Buildamin-heapH[1..k]fromA1[1],A2[1],...,Ak[1] //由k個(gè)序列頭建堆fori?1tok ifH[i]=Aj[1] thenQ[i]?j //記住堆中第i個(gè)數(shù)是從第j個(gè)序列來的。 endifendforforj?1tok head[j]?2 //head[j]是序列Aj中當(dāng)前剩余部分的首項(xiàng)，即最小數(shù)的位置。endfor i?0 //用于輸出序號(hào)heap-size?kwhileheap-size10 i?i+1 C[i]?H[1] //C是輸出序列。 j?Q[1] p?head[j] ifAj[p]1￥ then H[1]?Aj[p] head[j]?p+1 else H[1]?H[heap-size] Q[1]?Q[heap-size] Heap-size?heap-size-1 endif ifheap-size>0 thenHeapify(H[1..heap-size],1) //注意，移動(dòng)H[k]時(shí)，Q[k]要相應(yīng)更新。 endifendwhileEnd因?yàn)槊枯敵鲆粋€(gè)數(shù)之后我們需要修復(fù)含有不超過k個(gè)元素的堆，其時(shí)間為O(lgk)，所以總的時(shí)間復(fù)雜度為O(nlgk)。大家熟知，數(shù)組A[1..n]形成的堆里，第i個(gè)數(shù)A[i](1≤i≤n)的左兒子、右兒子、及父親的所在位置可以由下面公式算出：Left(A[i])=A[2i]Right(A[i])=A[2i+1]Parent(A[i])=A[?i/2?]但是我們很多時(shí)侯不能把這個(gè)堆存放在從A[1]開始的數(shù)組中，而是存放在從A[p]開始的n個(gè)單元中，即存放在A[p..r]中，這里r=p+n–1。這相當(dāng)于把這n個(gè)數(shù)在數(shù)組中向右平移了(p-1)個(gè)位置。請給出在這種情況下，確定數(shù)字A[i](p≤i≤r)的左兒子、右兒子、及父親的所在位置的公式。解: 我們把A[p..r]一一對應(yīng)地映射到另一個(gè)數(shù)組B[1..n]中，A[i]=B[i-p+1]，p≤i≤r，而B[j]=A[j+p-1]，1≤j≤n。因此新的公式是：Left(A[i])=Left(B[i-p+1])=B[2(i-p+1)]=B[2i-2p+2]=A[2i–p+1]，Right(A[i])=Right(B[i-p+1])]=B[2(i-p+1)+1]=B[2i–2p+3]=A[2i–p+2]，Parent(A[i])=Parent(B[i-p+1])=B[?(i-p+1)/2?]=A[?(i-p+1)/2+p-1]=A[?(i+p-1)/2?]。證明一個(gè)有n個(gè)數(shù)字的堆的左子樹最多含有2n/3個(gè)結(jié)點(diǎn)。證明: 如下圖所示，我們用L代表左子樹中的結(jié)點(diǎn)數(shù)，用R代表右子樹中的結(jié)點(diǎn)數(shù)。在左子樹中，我們用B代表在底層的葉子結(jié)點(diǎn)數(shù)，而用U代表底層上面的結(jié)點(diǎn)數(shù)，L=U+B。顯然，我們有關(guān)系B≤U+1和U≤R。因而得到L=U+B≤2U+1≤2R+1。因?yàn)長+R+1=n，所以R=n–L-1。從而有L≤2R+1≤2(n–L-1)+1=2n-2L-1<2n-2L，也就是L<2n/3，即L2n/3。假設(shè)給定一個(gè)n個(gè)數(shù)的數(shù)組A[1..n]和一個(gè)常數(shù)x。我們希望確定數(shù)組中是否存在兩個(gè)數(shù)，A[i]和A[j](1i<jn)，使得A[i]+A[j]=x。設(shè)計(jì)一個(gè)復(fù)雜度為O(nlgn)的算法解決這個(gè)問題。如果這樣兩個(gè)數(shù)存在，則報(bào)告這兩個(gè)數(shù)，否則報(bào)告不存在。解: 主要思路如下。我們先將數(shù)組A[1..n]從左到右排序?yàn)锳[1]≤A[2]≤A[3]≤…≤A[n]。然后把最小的數(shù)和最大的數(shù)相加(開始是A[1]和A[n]相加)。如果其和等于x，則問題解決。如果其和小于x，則最小的數(shù)不可能在解之中而丟棄。如其和大于x，則最大的數(shù)不可能在解之中而丟棄。每次我們從左丟棄一個(gè)最小數(shù)或從右丟棄一個(gè)最大數(shù)直至找到答案。Search-SUM(A[1..n]，x)Heap-sort(A[1..n])使得A[1]≤A[2]≤A[3]≤…≤A[n]exist?falsei?1j?nwhilei<jandexist=false ifA[i]+A[j]=x then return(true,i,j) else ifA[i]+A[j]<x theni?i+1 elsej?j-1 endif endifendwhilereturn(nosolution)End因?yàn)榕判蛐枰狾(nlgn)時(shí)間而以后的搜索只需要O(n)時(shí)間，上面算法的復(fù)雜度是O(nlgn)。錦標(biāo)賽排序法是一個(gè)基于比較的排序算法。它可以用一個(gè)稱之為錦標(biāo)賽樹(tournamenttree)的完全二叉樹來描述。這個(gè)二叉樹要求正好有n個(gè)葉子來存儲(chǔ)n個(gè)要排序的數(shù)字，并且所有葉子在底層或倒數(shù)第2層。下面是一個(gè)有5個(gè)葉子的一個(gè)錦標(biāo)賽樹圖例。9924710算法開始前，被排序的n個(gè)數(shù)字被放在這n個(gè)葉子中。每個(gè)內(nèi)結(jié)點(diǎn)代表一次比較。每次比較中勝者，即較小的數(shù)，參加下一輪在其父結(jié)點(diǎn)處的比較。在每個(gè)內(nèi)結(jié)點(diǎn)處，當(dāng)它的兩個(gè)子結(jié)點(diǎn)處的比較有了結(jié)果之后，該結(jié)點(diǎn)處的比較即可進(jìn)行。最后，在根結(jié)點(diǎn)處的比較決出冠軍，即最小的數(shù)。因?yàn)橐还灿?n-1)個(gè)內(nèi)結(jié)點(diǎn)，所以只需(n-1)次比較便可以找到最小數(shù)。當(dāng)最小的數(shù)被確定后，即可把它送到輸出序列中。另外，把它原來所在的葉子中的值改為。顯然，重復(fù)上面的過程可得到下一個(gè)最小的數(shù)。如果重復(fù)所有在內(nèi)結(jié)點(diǎn)處的比較去找下一個(gè)最小的數(shù)，我們又需要(n-1)次比較。這個(gè)復(fù)雜度太高。請?jiān)O(shè)計(jì)一個(gè)只需O(lgn)次比較的算法去找下一個(gè)最小的數(shù)。(只須解釋步驟，不要求偽碼。)請用偽碼設(shè)計(jì)一個(gè)用數(shù)組來實(shí)現(xiàn)錦標(biāo)賽排序的算法，使其復(fù)雜度為O(nlgn)。解：在找下一個(gè)最小數(shù)時(shí)，如果我們重復(fù)所有在內(nèi)結(jié)點(diǎn)的比較的話，那么，在大部分結(jié)點(diǎn)處所比較的兩個(gè)數(shù)仍然是在找前一個(gè)最小數(shù)時(shí)進(jìn)行過比較的兩個(gè)數(shù)，這部分比較不需再做。那么，在哪些結(jié)點(diǎn)處所比較的兩個(gè)數(shù)會(huì)有變化呢？容易看出，可能有變化的結(jié)點(diǎn)必定是在從前一個(gè)最小數(shù)所在的葉子到根的這條路徑上。所以我們的算法是，在每個(gè)結(jié)點(diǎn)處記錄每次比較后誰是勝者、誰是敗者。然后在找下一個(gè)最小數(shù)時(shí)，沿著前一個(gè)最小數(shù)所在的葉子到根的這條路徑，在每個(gè)結(jié)點(diǎn)處作一次比較。最后，在根結(jié)點(diǎn)處比較的勝者為下一個(gè)最小數(shù)。因?yàn)橛衝個(gè)葉子的這個(gè)二叉樹的高度是lgn，所以這條路最長為lgn。因此，找下一個(gè)最小的數(shù)最多只需lgn-1=O(lgn)次比較。假設(shè)要排序的n個(gè)數(shù)放在數(shù)組A[1..n]中。我們用數(shù)組W[1..2n-1]來代表錦標(biāo)賽樹的結(jié)點(diǎn)，做法和堆完全一樣。一開始，這n個(gè)被排數(shù)放在從W[n]到W[2n-1]之中而W[1..n-1]為空。然后從W[n-1]開始到W[1]為止，在每一個(gè)內(nèi)結(jié)點(diǎn)處做比較以求得最小數(shù)。我們用數(shù)組W[1..n-1]記錄各次比較的勝者。排好序的n個(gè)數(shù)輸出在數(shù)組C[1..n]中。在結(jié)點(diǎn)W[i]，1in-1，比較的兩個(gè)數(shù)分別從它兩個(gè)子結(jié)點(diǎn)的勝者，即W[2i]和W[2i+1]，中取得。在求得最小數(shù)之后，把它所在葉結(jié)點(diǎn)的值改為。然后，按照(a)中敘述辦法求得第2小數(shù)，第3小數(shù)，直至排序完成。為了能找到最小數(shù)所在葉結(jié)點(diǎn)位置，每次比較時(shí)記錄的是勝者在原序列A中的序號(hào)而不是數(shù)值本身。下面是實(shí)現(xiàn)這一算法的偽碼。因?yàn)檎业阶钚?shù)需要O(n)時(shí)間，而以后每找下一個(gè)最小數(shù)只需要O(lgn)時(shí)間，整個(gè)排序需要O(nlgn)時(shí)間。Tournament-sort(A[1..n],W[1..2n-1],C[1..n]) fori?1ton W[i+n-1]?i //數(shù)組A的序號(hào)依次放入W[n]到W[2n-1]之中endforforj?(n-1)downto1 left?W[2j] //W[j]的左兒子 right?W[2j+1] //W[j]右左兒子 ifA[left]A[right] thenW[j]?left elseW[j]?right endifendforwinner?W[1]C[1]?A[winner] //找到了最小數(shù)并輸出，winner是在原數(shù)組A中序號(hào)A[winner]?fori?2ton //順序找出下一個(gè)最小數(shù) j?winner+n-1 //最小數(shù)在數(shù)組W中位置 p?j/2 //最小數(shù)的父親 whilep0 left?W[2p] right?W[2p+1] ifA[left]A[right] thenW[p]?left elseW[p]?right endif p?p/2 //p的父親 endwhile winner?W[1] C[i]?A[winner] //找到笫i個(gè)最小數(shù)并輸出 A[winner]?endforEnd給定一個(gè)數(shù)組A[1..n]，我們希望建一個(gè)有n個(gè)內(nèi)結(jié)點(diǎn)的完全二叉樹T。它滿足以下條件：T的根中存有數(shù)組A[1..n]中最小的數(shù)。假設(shè)根中的數(shù)為A[r]，那么根的左子樹由數(shù)組A[1..r-1]中數(shù)遞歸建立，而根的右子樹由數(shù)組A[r+1..n]中數(shù)遞歸建立。當(dāng)數(shù)組為空時(shí)，對應(yīng)的子樹為葉結(jié)點(diǎn)而過程停止。讓我們稱這樣的二叉樹為最小優(yōu)先樹。下面圖示給出一個(gè)例子。畫出對應(yīng)于下面序列的最小優(yōu)先樹：6，5，2，9，7，1，3，10，9。解:設(shè)計(jì)一個(gè)構(gòu)造最小優(yōu)先樹的算法，其平均復(fù)雜度為O(nlgn)。我們假設(shè)最小數(shù)出現(xiàn)在序列中任何位置的概率相同。(注：可以有O(n)算法)解：調(diào)用下面分治算法可為數(shù)組A[1..n]構(gòu)造最小優(yōu)先樹。min-first(A[p,r],T)ifp>r then returnaleaf else findqsuchthatA[q]=min{A[p],A[p+1],…,A[r]} min-first(A[p,q-1],T1) min-first(A[q+1,r],T2) constructT(root=A[q],lefttree=T1,righttree=T2) returnTendifEnd數(shù)組A[1..n]的最小優(yōu)先樹可以通過調(diào)用min-first(A[1,n],T)得到。這個(gè)算法與快排序遞歸過程完全一樣。不同的只是，快排序是找到中間點(diǎn)后劃分序列為兩段，而最小優(yōu)先樹是找到最小數(shù)后將原序列分為兩段。因?yàn)閮伤惴ǖ膭澐植襟E都需要(n-1)次比較，所以上面算法與快排序的復(fù)雜度相同。他們的平均復(fù)雜度均為Q(nlgn)。如圖所示，平面上有上、下兩條平行線。每條線上各自分布有n個(gè)點(diǎn)，并從左到右順序標(biāo)為1，2，…，n。我們把上面的n個(gè)點(diǎn)與下面的n個(gè)點(diǎn)配成一一對應(yīng)的n個(gè)對子后，用一個(gè)直線段把每對點(diǎn)連上。若上面的點(diǎn)i與下面的點(diǎn)k相連，則記為k=π(i)(1≤i,k≤n)。如果i<j但π(i)>π(j)，那么線段(i,π(i))和線段(j,π(j))會(huì)有交叉點(diǎn)。例如，在下圖中一共有10個(gè)交點(diǎn)。請?jiān)O(shè)計(jì)一個(gè)O(nlgn)的算法，對一個(gè)給定的n對連結(jié)線段(i,π(i))(1≤i≤n)，計(jì)算出一共有多少個(gè)交叉點(diǎn)。解：我們用類似合并排序的方法對序列π(i)(1≤i≤n)一邊排序，一邊計(jì)數(shù)。我們把序列π(p..r)平分為π(p..q)和π(q+1..r)后，分別統(tǒng)計(jì)各子序列中的交叉點(diǎn)數(shù)并將序列排序。然后，在把二序列合并為一個(gè)序列時(shí)，如果左序列中首項(xiàng)L[i]比右序列的首項(xiàng)R[j]小，那么L[i]對應(yīng)的線段(i,π(i))與右序列中任一個(gè)線段不會(huì)有交點(diǎn)，L[i]從左序列中輸出后，i加1。否則，R[j]與當(dāng)前左序列中所有線段都有交點(diǎn)，在R[j]從右序列中輸出后，j加1，同時(shí)加上交點(diǎn)個(gè)數(shù)。 Merge-and-Count(,p,q,r,c) //合并π[p..q]和π[q+1..r]的子程序，c是交點(diǎn)個(gè)數(shù)n1q-p+1 //左序列中數(shù)字個(gè)數(shù)n2r-q //右序列中數(shù)字個(gè)數(shù)fori1ton1 L[i][p+i-1] //Copy左序列π[p..q]到L[1..n1]endforforj1ton2 R[j][q+j] //Copy右序列π[q+1..r]到R[1..n2]endforc0 //交叉點(diǎn)數(shù)初值ij1kp //順序?qū)俪鯷p..r]whilein1andjn2 ifL[i]<R[j] then [k]L[i] ii+1 else [k]R[j] cc+(n1–i+1) jj+1 endif kk+1endwhileifi>n1 then whilejn2 [k]R[j] jj+1 kk+1 endwhile else whilein1 [k]L[i] ii+1 kk+1 endwhileendifReturn(c) 分治算法的主程序如下：Mergesort-and-Count(,p,r,c)ifp=r thenreturn(c=0) else q(p+r)/2 Mergesort-and-Count(,p,q,cl) Mergesort-and-Count(,q+1,r,cr) Merge-and-Count(,p,q,r,cm) ccl+cr+cmendifreturn(c)End當(dāng)我們置p=1，r=n時(shí)，Mergesort-and-Count(,1,n,c)輸出這n個(gè)線段的交點(diǎn)數(shù)c。每個(gè)內(nèi)結(jié)點(diǎn)都有兩個(gè)兒子的二叉樹稱為完全二叉樹。設(shè)L為一個(gè)完全二叉樹T的葉子的集合。用數(shù)學(xué)歸納法證明以下等式:x∈L12depthx=(depth(x)表示x的深度，即從根到點(diǎn)x的路徑長度。) 證明：我們對樹的高度進(jìn)行數(shù)學(xué)歸納。 歸納基礎(chǔ)：當(dāng)h=0時(shí)，樹T中只有一個(gè)結(jié)點(diǎn)，通常視為葉子。因?yàn)樗纳疃葹?，顯然有120當(dāng)h=1時(shí)，樹T中只有一個(gè)根結(jié)點(diǎn)和兩個(gè)深度為1的葉子。因?yàn)?21+歸納步驟：假設(shè)當(dāng)h=0,1,…,k時(shí)，要證的等式成立?，F(xiàn)在證明當(dāng)h=k+1時(shí)等式也成立。因?yàn)門是完全二叉樹，它的兩個(gè)子樹也是完全二叉樹，但高度小于或等于k。我們用L-left表示左子樹中的葉子集合，用L-right表示右子樹中的葉子集合，L=L-leftL-right。因?yàn)閐epth(x)–1是x在左子樹（或右子樹）中的深度，由歸納假設(shè)，我們有：x∈L-left12x∈L-right1因此，我們有：x∈L12depthx=12x∈L-left12=12+12歸納成功。設(shè)T為一個(gè)高度為h的完全二叉樹，而它的所有結(jié)點(diǎn)的集合是V。用數(shù)學(xué)歸納法證明以下不等式: xV12證明： 我們對樹的高度h進(jìn)行數(shù)學(xué)歸納。歸納基礎(chǔ):當(dāng)h=0時(shí)，樹T中只有一個(gè)結(jié)點(diǎn)，通常視為葉子。因?yàn)樗纳疃葹?，顯然有120=1=當(dāng)h=1時(shí)，樹T中只有一個(gè)根結(jié)點(diǎn)和兩個(gè)深度為1的葉子。因?yàn)?20+121+12歸納步驟:假設(shè)當(dāng)h=0,1,…,k，(k1),時(shí)要證的等式成立?，F(xiàn)在證明當(dāng)h=k+1時(shí)等式也成立。因?yàn)門是完全二叉樹，它的兩個(gè)子樹也是完全二叉樹，但高度小于或等于k。我們用h-left和h-right分別表示左子樹和右子樹的高度，則有h-leftk，h-rightk。我們用L表示左子樹中所有結(jié)點(diǎn)的集合，用R表示右子樹中的所有結(jié)點(diǎn)的集合，V={root}LR。因?yàn)閐epth(x)–1是x在左子樹（或右子樹）中的深度，由歸納假設(shè)，我們有：xL12depthx-1h-left+xR12depthx-1h-right因此，我們有：xV12depth(x)=1+12xL12depthx-1+12xR12depthx-1

=(k+1)+1=h+1。歸納成功。 重新考慮第8題的k-路合并問題。假設(shè)A1,A2,...Ak是k個(gè)排好序的序列。序列Ai有ni個(gè)數(shù)(1≤i≤k)并且有n1+n2+…+nk=n。下面的分治算法k-merge(A,i,j,B,m)把Ai到Aj(1≤i≤j≤k)的序列合并為單一的排好序的序列B。這里，m=h=ijnh是序列B中數(shù)字的個(gè)數(shù)。調(diào)用k-merge(A,1,k,B,n)則可把A1,A2,...Ak合并為單一的排好序的序列B。假設(shè)合并一個(gè)有p個(gè)數(shù)的序列和一個(gè)有q個(gè)數(shù)的序列需要（p+q-1）次比較，請為算法k-merge(A,i,j,B,m)的復(fù)雜度建立一個(gè)遞推關(guān)系并證明k-merge(A,1,k,B,n)的復(fù)雜度是O(nlgk-merge(A,i,j,B,m) //TheoutputisinB[1..m]，1≤i≤j≤k ifi=j then mni B[1..m]Ai[1..ni] else mid(i+j)/2 k-merge(A,i,mid,B1,m1) k-merge(A,mid+1,j,B2,m2) mm1+m2 Merge(B1[1..m1],B2[1..m2],B[1..m]) //合并B1和B1為序列B endifEnd解： 我們用T(i,j)表示把Ai到Aj合并所需的時(shí)間。我們可得以下遞推關(guān)系：T(i,j)=T(i,mid)+T(mid+1,j)+O(m)，如果i<j，這里，m=h=ijnT(i,i)=O(ni)。從以上遞推關(guān)系，可見存在常數(shù)c使得 T(i,j)<T(i,mid)+T(mid+1,j)+cmT(i,i)<cni。 現(xiàn)在證明，T(i,j)≤cm(lgh+1)，這里，h=j-i+1是所合并的序列的個(gè)數(shù)。我們對h進(jìn)行數(shù)學(xué)歸納。歸納基礎(chǔ)：當(dāng)h=1，已知T(i,i)<cni=cm，故命題成立。歸納步驟：當(dāng)h=j–i+1>1時(shí)，記h1=mid–i+1=h/2，和h2=j–mid=h/2。由歸納假設(shè)，我們有：T(i,mid)cm1(lgh1+1)，這里，m1=h=imidT(mid+1,j)cm2(lgh2+1)，這里，m2=h=mid+1j再由遞推關(guān)系，可得：T(i,j)<T(i,mid)+T(mid+1,j)+cm //m1+m2=m≤cm1(lgh1+1)+cm2(lgh2+1)+cm我們分兩種情形。 h是偶數(shù)。我們有h1=h2=h/2。T(i,j)<cm1(lgh1+1)+cm2(lgh2+1)+cm=cm1(lg(h/2)+1)+cm2(lg(h/2)+1)+cm=cm1(lgh-1+1)+cm2(lgh-1+1)+cm=cm1lgh+cm2lgh+cm=cmlgh+cm=cm(lgh+1)。h是奇數(shù)。我們有h1=(h+1)/2和h2=(h-1)/2。由遞推關(guān)系，可推導(dǎo)如下：T(i,j)<T(i,mid)+T(mid+1,j)+cm <cm1(lgh1+1)+cm2(lgh2+1)+cm=cm1(lg(h+1)-1+1)+cm2(lg(h-1)-1+1)+cm=cm1lg(h+1)+cm2lg(h-1)+cm=cm1lgh+cm2lg(h–1)+cm //因?yàn)閔是奇數(shù)時(shí)，lg(h+1)=lgh。cm1lgh+cm2lgh+cm =cm(lgh+1)。歸納成功。當(dāng)h=k,m=n時(shí)，k-merge(A,1,k,B,n)有復(fù)雜度O(nlgk)。假設(shè)數(shù)組A[1..n]是一個(gè)堆。請?jiān)O(shè)計(jì)一個(gè)O(lgn)的算法，對任一個(gè)元素A[i]，它可以找出并打印出在對應(yīng)的二叉樹中，從根A[1]到A[i]的這條路徑。用left和right表示每一步的走向。例如，在下面的堆里，A[10]的路經(jīng)是root,left,right,left。15157238138106512345678910解： 我們給出一個(gè)用分治法的算法如下：Print-Path(A[1..n],i) //OutputthepathfromroottoA[i]ifi=1 then print“root” else fatheri/2 Print-Path(A[1..n],father) ifi=2father then print“，left” else print“，right” endifendifEnd 顯然算法是正確的。因?yàn)槁窂介L是O(lgn)，所以復(fù)雜度是O(lgn)。證明，在最壞情況時(shí)，3.3.3節(jié)中建堆的算法Build-Max-Heap(A[1..n],1)需要至少2n-2lg(n+1)次比較。解： 我們只需證明，在一個(gè)特例中，Build-Max-Heap(A[1..n],1)需要至少2n-2lg(n+1)次比較。我們置n=2h+1-1，那么A[1..n