算法設(shè)計與分析課后習(xí)題

1、第一章1 .算法分析題算法分析題1-1求下列函數(shù)的漸進(jìn)表達(dá)式(1) .3nA2+i0n5是，nA2=1時，nA2/102An故：nA2/10+2An2An+2人門=2*2人門=0(2八門)(3) .21+1/n21+1=22=0(1)(4) .log(nA3)=3log(n)=O(log(n)(5) .1010g(3人丹=(10log3)n=0(n)算法分析題1-6(1)因為：f(n)=log(nA2)=2log(n);g(n)=log(n)+5所以：f(n)=O(og(n)+5)=9(g(n)(2)因為：log(n)vn;f(n)=2log(n);g(n)=vn所以：f(n)=O(g(n)(

2、3)因為：log(n)n;f(n)=n;g(n)=10gA2)=2log(n)所以；f(n)=Q(g(n)(4)因為：f(n)=nlogn+n;g(n)=logn所以：f(n)=Q(g(n)(5)因為：f(n)=10;g(n)=log(10)所以:f(n)=Og(n)(6)因為：f(n)=logA2(n);g(n)=log(n)所以：f(n)=Q(g(n)(7)因為：f(n)=2Annn人2所以：f(n)=Q(g(n)(8)因為：f(n)=2An;g(n)=3An;2An因此，Tmax(N)=Q(Tavg(N)=Q(O(f(n)=Q(f(n).弟早算法分析題2-3設(shè)a0:n-1是已經(jīng)排好序的數(shù)

3、組。請改寫二分搜索算法，似的當(dāng)搜索元素x在數(shù)組中時，返回小于x的最大元素位置i和大于x的最小元素位置j。當(dāng)搜索元素在數(shù)組中時，i和j相同，均為x的位置。分許與解答：改寫二分搜索算法如下：typedefintTYPE_t;/* Functionname:BinarySearch* Parameters:* ilndex代表i的位置，即最大元素位置；* jlndex代表j的位置，即最小元素位置；* aArr:代表數(shù)組a,且有序* xVar:代表元素x;* aLen:代表數(shù)組元素個數(shù)；* Returnvalue:* 0:執(zhí)行成功，最大元素位置和最小元素位置不等* 1:執(zhí)行成功，最大元素位置和最小元素

4、位置相等*/staticintBinarySearch(TYPE_taArr,intnLen,TYPE_txVar,int*ilndex,int*jlndex)(intleft=0;intright=nLen-1;intmiddle=(left+right)/2;while(leftaArrmiddle)left=middle+1;elseright=middle-1;middle=(left+right)/2;*ilndex=right;*jlndex=left;return0;算法分析題2-6對任何非零偶數(shù)n,總可以找到奇數(shù)m和正整數(shù)k,使得n=m*2”.為了求出2個n階矩陣的乘積，可以把

5、一個n階矩陣劃分成mxm個子矩陣，每個子矩陣2”x2Ak個元素。當(dāng)需要求2x2”的子矩陣的積時，使用Strassen算法。設(shè)計一個傳統(tǒng)方法與Strasssen算法相結(jié)合的矩陣相乘算法，對于任何偶數(shù)n,都可以求出2個n階矩陣的乘積。并分析算法的計算時間復(fù)雜度。分析與解答：將n階矩陣分塊為mxm的矩陣。用傳統(tǒng)方法求2個m階矩陣的乘積需要計算O(m3)次2個2”x2Ak矩陣的乘積。用Strassen矩陣乘法計算2個2”x2Ak的矩陣的乘積需要的計算時間為O(7Ak),因此算法的計算時間為O(7Ak*mA3).算法分析題2-9設(shè)T0,n-1是n個元素的數(shù)組。對任一元素x,設(shè)S(x)=i|Ti=x.當(dāng)|

6、S(x)|n/2時，稱x為T的主元素。設(shè)計一個線性時間算法，確定T0:n-1是否有一個主元素。分析與解答：如果T有一個主元素x,則x是T的中位數(shù)。反之，如果T的中位數(shù)不是T的主元素，則T沒有主元素。下面算法設(shè)計為在一個線性時間中找中位數(shù)：typedefintT;#defineYESMIDDLEELEMENT1#defineNOMIDDLEELEMENT0/*Functionname:IsExistMiddleElement*Parameters:aArr:表示數(shù)組T0:n-1n:表示數(shù)組長度x:表示要判斷的數(shù)x,是否主元素*keyIndex:表示主元素在數(shù)組中的下標(biāo)*Return:YESMID

7、DLEELEMEN俵示找至UNOMIDDLEELEMENT:表示沒有找至U*/staticintIsExistMiddleElement(TaArr,intn,Tx,int*keyIndex)intmiddleKey=n/2;inti=0;for(i=0;imiddleKey)*keyIndex=i;returnYES_MIDDLE_ELEMENT;)*keyIndex=-1;returnNO_MIDDLE_ELEMENT;)算法分析題2-14對所給元素存儲于數(shù)組中和存儲于鏈表中2中情形，寫出自然合并排序算法。分析與解答：自然合并排序是合并排序算法的一種改進(jìn)。自然合并排序，對于初始給定的數(shù)組，

8、通常存在多個長度大于1的已自然排好序的子數(shù)組段。例如，若數(shù)組a中元素為4,8,7,1,5,6,2,則自然排好序的子數(shù)組段有4,8,3,7,1,5,6,2.用一次對數(shù)組a的線性掃描就足以找出所有這些排好序的子數(shù)組段。然后將相鄰的排好序的子數(shù)組段兩兩合并，構(gòu)成更大的排好序的子數(shù)組段3,4,7,8,1,2,5,6.繼續(xù)合并相鄰排好序的子數(shù)組段，直至整個數(shù)組已經(jīng)排好序。算法設(shè)計及代碼實現(xiàn)：(1).數(shù)組實現(xiàn)法：#defineDEBUG1typedefinttype_t;staticvoidDatasetMerge(type_t*arr,intleft,intbetween,intright)inti,k

9、;intbegin1,end1,begin2,end2;type_t*tmpArr;begin1=left;/*第一個排好序的初始位置*/end1=between;/*第一個排好序的結(jié)束位置*/begin2=between+1;/*第二個排好序的初始位置*/end2=right;/*第二個排好序的結(jié)束位置*/tmpArr=malloc(sizeof(type_t)*(right-left+1);if(!tmpArr)return;k=0;/* 比較兩個指針指向的元素，選擇相對小的元素放入合并空間* 并移動指針到下一個位置* /while(begin1=end1)&(begin2=end2)if

10、(arrbegin1arrbegin2)tmpArrk=arrbegin1;begin1+;elsetmpArrk=arrbegin2;begin2+;)k+;)/*x如果第一個序列有剩余，直接拷貝到合并數(shù)組的序列中* /while(beginl=end1)tmpArrk+=arrbegin1+;)/* 如果第二個序列有剩余，直接拷貝到合并數(shù)組的序列中*/while(begin2=end2)tmpArrk+=arrbegin2+;)/* 拷貝臨時數(shù)組序列到原數(shù)組中*/for(i=0;i=(right-left);i+)arrleft+i=tmpArri;)free(tmpArr);)voidD

11、atasetNatureMerge(type_tarr,intn)int*tmpArr;inti,k=0;ints=1;intgroup;/*記錄分割組的數(shù)目*/intcount=0;intleft,between,right;intarrLen=n;/*tmpArr用來存儲數(shù)組元素下標(biāo)分割點*/tmpArr=(int*)malloc(n*sizeof(int);if(!tmpArr)return;)memset(tmpArr,-1,(n*sizeof(int);/*存儲首分割點*/tmpArrk+=0;for(i=0;iarri+1)tmpArrk=i;k+;/*存儲尾分割點*/tmpArr

12、k=n-1;/*k和group分別記錄分割數(shù)組長度*/group=k;#ifDEBUGprintf(n數(shù)組分割點為：n);printf(t);for(i=0;ik)right=k;DatasetMerge(arr,tmpArrleft,tmpArrbetween,tmpArrright);/*進(jìn)行生下來的合并*/for(i=1;ik)right=k;DatasetMerge(arr,tmpArrleft+1,tmpArrbetween,tmpArrright);s+=s;free(tmpArr);(2).鏈表實現(xiàn)法：#ifLINKtypedefstructnode*link_t;structn

13、odeintitem;link_tnext;link_tLinkMerge(link_ta,link_tb)link_tc,head;c=head=malloc(sizeof(structnode);while(a!=NULL)&(b!=NULL)if(a-itemitem)c-next=a;c=a;a=a-next;elsec-next=b;c=b;b=b-next;c-next=(a=NULL)?b:a;returnhead-next;link_tLinkNuturalMergesort(link_tt)link_ta,b;link_tu,v;QUEUEQ;if(t=NULL|t-next=NULL)