k 因此對所有正整數N命題均成立。此題同樣通過數學歸納法證明。注意到12，即121N=1Fk1FkFk

kk1(12)k1k 1.10(a)(2i1)2i1N(N1)NN N i3(N1)3

(N1)3N2(N4(N1)2[N24

2N24N4(N1)[ 4(N1)2(N2)2[(N1)(N2NN ，N，NloglogN，NlogN，Nlog(N2)，N15，N2，N2logNNN32N/22N。NlogNNlog(N2不成立，一個反例為T1(N)2N,T2(N) ，而f(N)不成立，一個反例為T1(NN2T2(N)Nf(NNNlogN增長更慢，為證明這一點，我們使用反證法：假設N/ 兩邊同取對數，得到(/ logN)*logN比loglogN增長更慢，第一個表達式實際上是 ，設L=logN，則有 比logL增長得更慢，即2L比log2L的更慢，但實際上我們知道log2Lo(L) limlogi

limilogi1N N

N

Nln2

定義當Nf(N)1，Nf(N)N，同樣，定義當N為奇數時g(N)運行時間為O(N2運行時間為O(N3運行時間為O(N2j最大可達到i2，i2N2，kjN2，因此可能的最大NN2N2，即O(N5由前面的分析，if語句被執行O(N3)i*iji個)為OjO(N2)，所以總共耗時為O(N4)。這個例子說明簡單的把各層循環的出）不是很顯然，這一算法的正確性可以通過數學歸納法證明，讀者可參閱JonBentley的《ProgrammingPearls《編程珠璣》）N=327種等可能的交A[i]O(i)時間，N/(N-i)，這個值由如下的步驟得出：Ni個是

N2 N21O(N2logNNiN

N

j個算法當N很大時會有激烈的增長，使它看起來不是線性的。(e)無法為第一、二種算法的運行時間找到一個界，因為對任意給定的時間T，算這些計算都建立在電腦具有足夠空間數組的前提下，算法4在N=1,000,000時只耗時3秒O(NlogN 整NN的素數的倒數之和，為O(NloglogN)，詳Knuth《計算機程序設計藝術》第二卷X2X4X8X10X20X40X60XX,X,X,...,X,X,X,...,

。N對N=0或N=10N>1b(N)N1的個數，B(b)法是，注意到如果前N-1個元素中有主要元素，則最后一個元素對結果沒有T(N)T(N)=T(N/2)+O(N)T(N)=O(N)（參見第十章保存一個數組AB的元素直接覆蓋在數組A上，每一我們可以把這個方法推廣到任意N對數字，在一個單位時間內計算出每對的和。2.22Low=1，High=2，則Mid=1題3.4中關于抽象性程度的建議在本題中被應用。程序如圖3.1（圖中注釋為：這個代碼可以通過用Retrieve和IsPastEnd替代L1Pos->Element求并集的函數Union3.4(a)一種算法是在計算的過程中始終保持結果按冪排列。MN個乘積中每一個都需要對為O(M2N2這些技巧使當M和N很大時算法得到明顯的加速，但運行時間顯然仍有O(Nmin(M,N))M=1時，顯然算法是線性的。VAX/VMSC編譯器的內存管理系統對這種情況下的的處理很糟糕，以致于表現出O(NlogN)的速度。3.12O(N)3.5中的方法和回收算法中使用的策略十分相似。在每次while循環中的第一條語句PreviousPosCurrentPos O(N3的時間界。更好的時間界為O(N2，注意到一個長為N的表最多有N個元O(N2，所以時間界為O(N2。

EES，用來執行Push和Pop操作，另一個棧，我們叫做M，用來記錄最小值。為了實現Push(X,E)Push(X,S)XM的棧頂元素小，那么同時Push(X,M)Pop(E)Pop(S)。如果彈出頂元素實現。所有這些操作都顯然是O(1)的這個證明需要第七章中排序一定會花費(NlogN)時間的結論。進行O(N)們三個不能同時需要O(1)時間。個，就需要移動它。一個合理的策略是把它移動到使它的中心距其他兩個棧棧Q->FrontQ->Rear，分別指向鏈表的首端和末端。程序的細GHI,LM(bD和(c)(d)(e)4節點都有一個從它的父節點指向它的指針，共有N-1個。剩下的就是NULL節點。節點。這2*(2k11)2k22個節點加上根節點便證明了H=k+1的情況，因此N為節點數，F為滿節點數，L為樹葉數，H為半節點（只有一個兒子的節點）數。很明顯，N=F+L+H，進2F+H=N-1（44）L-F=1。k+1i個節點的左子樹和一個1。如果沒有只有一個兒子最終會得到一個只有一個節點的樹，它的和為11。(a)-**ab+cd(b)((a*b)*(c+d))–e(c)ab*cd+*e–

這個問題和鏈表的游標法實現差異不大。我們一個數組，每個數組元素由一個該節點值的域和兩個分別為left和right的整數組成。Thelistcanbe和CursorDispose例程，代替malloc和。一個位數組BiB[i]truefalse。不斷產生隨機數知道找到一個不在樹上的數。如果樹上有N個元素，那么有M-N個數不在樹上，所以找到一個不在樹上的數的概率是(M-N)/M，因此嘗試次數的數學期望為每次產生出滿足條件的數概率是N/M，所以次數的數學期望是M/N=α。insertdelete操作的總花費是α/(α-1)+α=1+α+1/(α-1)。α=2時取N(0)=1,N(1)=2,N(H)=N(H-1)+N(H-2)+N(H)=F(H+2)-=F(N-1)+F(N-k=H+1時，分析如下：2H12H1位于根，且右子樹是一個含有2H112H12H1個，也就是第2H到第2H2H11個插入操作2H11到2H2H11這一段連續的整數插入形成的，正好有2H1次插入在根產生了不平衡，引起一次單旋轉。容易驗證這次單旋轉使2H成為新的根，并形成了一個高為H-1的完全平衡的左。剛剛插入的新元素依附在高度為H-2的完全平衡的右上。因此右正好可以看成是2H1到2H2H1被依2H2H112H11這些數的插入會

(a)(a)(a)(a-c)RandInt(Lower,Upper)，在一個適當的間隔里產生均勻分布的隨機數。當N不是正數，或過大使得空間不足時，MakeRandomTree返回NULL。釋為：錯誤處理已被忽略；見習題4.29）, 另法模仿前一道習題的思路，不同之處是兩個的高度都是H-1。這種方不存在符合條件的節點O(logN)O(KlogN)的時間4.35將根放在一個空隊列，然后不斷從隊列出節點并把這個節點的左右兒子（如果時間，共有N個出隊列和N個入隊列操作。

如下所示的函數顯然有線性的時間界，因為情況下它會遍歷T1和T2T2的根節點的序號為x，就在T1中找到同為x的節點并且旋轉至根部。對T1的左和右遞歸的運用這個策略（T2左和右的根節點的值。如果dNx的深度，那么運行時間滿足T(N)T(i)T(Ni1)dN，其中i是左的大小。在情況下，dN總是O(N)，i總是0，所以運行時間是二次的。假設i個遞推式的解。若更合理地假設dN是O(logN)，那么運行時間將是O(N)。(a)1989無法插入到表中，因為hash2(1989)65,1,73都已經再散列時，表的大小選為一個大致是原表兩倍的素數。在這道題中，合適的大小為19，相應的散列函數h(x)=x(mod19)。5.4須對頻繁的再散列特別謹慎。設p為即將再散列為一個更小的表的臨界狀態pN次刪除之后，都會引起再一次再散列。為了平衡兩種可能的花銷，如果我們知道插入操作將比刪除操作更頻繁，這個p可能是偏大的。如果p太接近若p=1.0，則（在臨界狀態時進行）交替的刪除和插入每一次都可以引起一次再散(b)消除了一次，但沒有消除二次，因為所有元素均使用同一種解決)以使用習題2.7中的方法。

MNO(MNlogMN)時間。如果通O(MN)的時O(M+NO((M+N)log(M+N))的時間內帶來改進。另一方面，如果預計輸出的多項式只有O(M+N)項，使用散列表可以節省大量的空間，因為在這個情況下散列表只需要O(M+N)的空間。1的位置，也不能保證這個單詞一定在詞典一個不在詞典里的單詞有10%的可能被散列至一個其值為1的位置。是短單詞）thenthem，不會有任WhereOnStack，并且維指向棧的有效部分，且被WhereOnStack所指的棧中的項是否有該位置的地址。6.1可以。當元素插入時，比較它和當前的最小值的大小，如果新元素較小則更改最小值。DeleteMin在這種體系中十分昂貴。 果遇到左兒子，將i乘以2，如果遇到右兒子，將i乘以2再加1。(aH(N)N個節點的完全二叉樹各節點高度之和，我們證明H(N)=N-b(N)，b(N)N1的個數。對N=0N=1的情況命題均成立。假設對k到N-1（含N-1）的每個值命題均成立。設左和右分別含L和R個節其中第二行由歸納假設得來，第三行由LRN1得來。最后一個節點要么在左，要么在右。如果在左，那么右就是一個完全二叉樹，則點在左則N的第二位一定是0。因此這種情況下，b(L)=b(N)，并且有H(N)=N–如果最后一個節點在右，則b(LlogN，R的二進制表示除了NN=27=101R=101–1，同樣有H(N)=N–為b的兒子。根的最大遞歸地轉化為2k1個元素的二叉堆。然后將堆的最后一個元素（它在N2k運行時間滿足T(N)2T(N/2)logN 。基準情況是T(8)=8。令D,D,..., )就是說堆的最后一層被填滿O(1N)

k引理：對k>1E(Dkpj,k(E(Dj)j證明：在左子堆中深度為d的元素在整個堆中的深度為d+1。由E(Dj1)E(Dj1由之前做過的假設，堆的最后一層是滿的，第二、第三、…、第k–10.5的概率在左子堆中（實際上，在 的概率應當為1121

N

概率應當為2

N

j k 2k2j 證明：使用數學歸納法證明。顯然k1或k2時定理成立。接著我們要證明對任意k>2，若命題對任意比k小的數成立，則命題對k成立。現在，由歸納假設，對任意的1jk1E(Dj)E(Dkj)logjlog(kx0f(xlogxJensenlogjlog(kj)2log(k/E(Dj)E(Dkj)log(k/2)log(k/pj,kpkj,kpj,kE(Dj)pkj,kE(Dkj)pj,klog(k/2)pkj,klog(k/

kE(Dk)pj,k(E(Dj)jk pj,kE(DjkE(Dk)1pj,klog(k/jk1log(k/2)pj1log(k/log)(a))(a)如果堆是最小堆，從根處的空穴開始，沿最小的兒子向下形成一條路徑直到樹葉，這大概要花費logNlogN個元素進行二分查找。這要花費O(loglogN)次比較。尋找最小兒子形成的路徑，在經過logN–loglogN層后停止。這時很容易決定loglogNlogNlogloglogN次比較。如果在上方，對logN–loglogN個元素進行二分查找。二分查找最多需loglogN次比較，路徑的時間界可以被改進到logNlog*NO(1)，其中log*NAckerman函數的反函數（見第8章。這個界可以在參考文獻[16]中找到。

(id2)d，其兒子在(i1)d2idd(a)O((MdN)logNdO((MN)logNO(MN2dmax(2,M/N(a)如果將DecreaseKey應用于一個十分深（十分“左”）的節點，上濾的時間將Insert來高效率的進行DecreaseKeyx，我們xxx的父節點到根的路徑只有logN個節點被影響，保證了時間界。在第11章中也有相關討論。CheritonTarjan[9]中有所探討。大致的思路是，如果根(a)標準的做法是把操作分解為幾個部分。每當第一個元素再次在出隊列的堆中出2*1*N2)個時間單元，因為有2*2*(N4)N4個對右路徑上至多只有兩2