數(shù)據(jù)結(jié)構(gòu)與算法分析語言描述前六章答案中文版

k 因此對(duì)所有正整數(shù)N命題均成立。此題同樣通過數(shù)學(xué)歸納法證明。注意到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不成立，一個(gè)反例為T1(N)2N,T2(N) ，而f(N)不成立，一個(gè)反例為T1(NN2T2(N)Nf(NNNlogN增長更慢，為證明這一點(diǎn)，我們使用反證法：假設(shè)N/ 兩邊同取對(duì)數(shù)，得到(/ logN)*logN比loglogN增長更慢，第一個(gè)表達(dá)式實(shí)際上是 ，設(shè)L=logN，則有 比logL增長得更慢，即2L比log2L的更慢，但實(shí)際上我們知道log2Lo(L) limlogi

limilogi1N N

N

Nln2

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

N2 N21O(N2logNNiN

N

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

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

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

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

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

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

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

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

N

概率應(yīng)當(dāng)為2

N

j k 2k2j 證明：使用數(shù)學(xué)歸納法證明。顯然k1或k2時(shí)定理成立。接著我們要證明對(duì)任意k>2，若命題對(duì)任意比k小的數(shù)成立，則命題對(duì)k成立?，F(xiàn)在，由歸納假設(shè)，對(duì)任意的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)如果堆是最小堆，從根處的空穴開始，沿最小的兒子向下形成一條路徑直到樹葉，這大概要花費(fèi)logNlogN個(gè)元素進(jìn)行二分查找。這要花費(fèi)O(loglogN)次比較。尋找最小兒子形成的路徑，在經(jīng)過logN–loglogN層后停止。這時(shí)很容易決定loglogNlogNlogloglogN次比較。如果在上方，對(duì)logN–loglogN個(gè)元素進(jìn)行二分查找。二分查找最多需loglogN次比較，路徑的時(shí)間界可以被改進(jìn)到logNlog*NO(1)，其中l(wèi)og*NAckerman函數(shù)的反函數(shù)（見第8章。這個(gè)界可以在參考文獻(xiàn)[16]中找到。

(id2)d，其兒子在(i1)d2idd(a)O((MdN)logNdO((MN)logNO(MN2dmax(2,M/N(a)如果將DecreaseKey應(yīng)用于一個(gè)十分深（十分“左”）的節(jié)點(diǎn)，上濾的時(shí)間將Insert來高效率的進(jìn)行DecreaseKeyx，我們xxx的父節(jié)點(diǎn)到根的路徑只有l(wèi)ogN個(gè)節(jié)點(diǎn)被影響，保證了時(shí)間界。在第11章中也有相關(guān)討論。CheritonTarjan[9]中有所探討。大致的思路是，如果根(a)標(biāo)準(zhǔn)的做法是把操作分解為幾個(gè)部分。每當(dāng)?shù)谝粋€(gè)元素再次在出隊(duì)列的堆中出2*1*N2)個(gè)時(shí)間單元，因?yàn)橛?*2*(N4)N4個(gè)對(duì)右路徑上至多只有兩2