輸出：實數(shù)anIfn=0Thenreturn1ElseIfn%2=0ThenreturnElsereturnT(n)=θ(1)ifn<1T(n)=T(n/2)+θ(1)ifn>=1MasterT(n)=θ(1)ifn<1T(n)=θ(logn)ifn>=1(b)Strassen//Strassen(A,B,n)n*nA//Strassen(A,B,n)ABStrassen(A,B,n)時間復雜度為T(n輸出：實數(shù)矩陣AnIfn=0ThenreturnEElseifn=1Thenreturn

Elseifn=2ThenreturnStrassen(A,A,n)StrassenA*A)Elseifn%2=0ThenreturnElsereturn時間復雜度分析

log

利用遞 得出，

T(n/2)

log7 2 3 t

log7)O(n*2)T(n/2log7)O(n*3)T(n/2log7//

t ,n2得，

n＝nlog7

*lg7

因此

nT

nlog

n1F(n+2)=1+i

F(i)成立設(shè)當n=k時 i

F(i)成立n=k+1，F(xiàn)(k+1+2)=1+k1F(i)iF(k+1+2)=F(k+2)+F(k+1)=1+i

F(i)+F(k+1)=1+k1in=k+1F(n+2)=1+i

2

設(shè)當n=k時,F(k+2)=(12

5k則現(xiàn)在需要證明當n=k+1時 F(k+3)=(12

)k

成立。 1

5k1 2 2 述等 輸入：自然數(shù)輸出：那契數(shù)列的第n項front<-1,rear<-1,temp<-Ifn<=1Thenreturn1Fori=2Tontemp<-front<-rear<-Return算法輸入：自然數(shù)輸出：那契數(shù)列的第n項Ifn<=1Thenreturn1ElsereturnFib2(n-1)+Fib2(n-T(n)=θ(1)ifT(n)=T(n-1)+T(n- ifn>1(3/2)nT(n)<(5/3)n故有T(n)=θ(1) ifn<=1T(n)=o((5/3)n) ifn>1.用中做了大量重復性工作，例執(zhí)行Fib2(n-1)的同時又計算了Fib2(n-2),這

１0１0

00

FF

FF

因此，利用

設(shè)計算法如下 Matrix[2][2]<-{1,1,1,0}輸出：那契數(shù)列的第n項值，即輸出Matrix[0][0]的Ifn=1n=0returnElseIfn%2=0returnElsereturn采用二分法來求那契數(shù)列，此時時間復雜度滿足T(n)=O(logn)方法：(1)將所有點按照x坐標排好序(2)對每一個點從前往后依次掃描Θ(n(n-1)/2)+Θ(nlgn)ifq=?(??+n1=q-n2=r-fori=1toforj=1to compareeachpointin[p,q-1]withpointin[q,r]andfindthefriendlypointpair,thenmarkit.算法開始前已將S中的點進行預(yù)排序（按x坐標遞增順序）算法復雜性為Θ(nlog??)，算法的遞歸式為T(n2T(n2(n2Master時間復雜度為邊，則必有 使即可，可以簡xypoints[n],left,輸出：構(gòu)成周長最角形的三個Ifleft=right||left+1=rightElseifIfReturnm1+m2+m3;//或者返回最角形的三個Elsereturnmid<-d1<-d2<-Fori=lefttoright&&|points[i].x-Tmp[m++]<-Fori=0toForj=i+1tom&& Ifd=m1+m2+m3//或者返回最角形的三個Returnd//或者返回最角形的三個S，P,Pi,Pj,PkS將凸多邊形p1p2...pn中其中一個點為原點，與其他各點相連并延長做射線，對于n個點就會形成n2個三角形區(qū)域，對于q1,q2...qn中每個點qi,利用二分查找判斷qi點在哪個三角形區(qū)域內(nèi)，時間復雜度為O(logn)若qi位于最左邊三角形左側(cè)或者根據(jù)三角形的第三條邊判斷該點是否在該三角形中，依次對q1,,q2...qn判斷，故判斷q1,q2...qn是否在凸多邊形內(nèi)的時間復雜度為O(nlogn輸入：凸多邊形的npoints1[n],np1Forq1toqBinaryFind(points1[n],qiIfqi位于p1,point1,point2ReturnStep1:遞歸地遍歷整棵樹T，以每個頂點i為父結(jié)點，尋找這棵子樹上dis(x,y)<τcount(i)。Step2:遍歷樹上的每個頂點，對所有子樹上的dis(x,y)<τ的頂點對個數(shù)count(i)dis(x,y)<=τcount(T)。偽代碼以孩子鏈表表示法表示樹TCount=P While(p childNumber p-w Count+=GetCount(T,childNumber,level-p p-Returncount;Count=GetCountOfOnePoint(T,p While(p Count GetCountOfTree(T,p-p p-ReturnXa=X[???2?Yb=Y[???2?與ba=b，a若a<b，則一定有X[0]＜X[1]<…<a<…<b<Y[???2?+1]<…<Y[n-1]。即中位數(shù)一定不在X中比a小的部分和Yb的部分。這樣可在X的子數(shù)組X[???2?:n-1]YY[0:???2?]中繼續(xù)尋找中位數(shù)。若a＞b，則一定有Y[0]＜…<b<…<a<X[???2?+1]<…<X[n-1]。即中位數(shù)一定不在Y中比b小的部分和X中比a大的部分這樣可在X的子數(shù)組X[0:???2?]和YY[???2?:n-1]中繼續(xù)尋找中位數(shù)。11/2O(logn)偽代碼描述：輸出：X和Y2nifendX-thenreturnifthenreturnelseifFindMediam(X,Y,0,n-1,0,n-1)1-7O(1)，8數(shù)，問題規(guī)模變?yōu)樵瓉淼囊话?，遞推為T(n)=T(n/2)+O(1)。MasterO(logn)合并過程中，設(shè)兩個待合并串分別為LRL[i]L[i]>R[j]，說明R[jL中剩余的L[i]的元素都小，并與這些元素可得出Acount=0,Createtemp[r-p+1]whilewhileleft<=qwhileright<=rreturnISMerge-thenISMerge-SortISMerge-ISMerge-return由于此算法是在Merge-Sort算法中，Merge階段增加了計數(shù)過程，該步驟復雜度為O(1)，因此，總得算法時間復雜度與合并排序算法相同，為S[i]，z=x-S[i],Sz,若Input：nS,S[1:n]Output:S中是否有兩個元素的和為xMerge-fori←1todoz←x-ifBinary-thenreturnreturnBinary-ifthenreturnifthenreturnelseifreturnBinary-Search(S,start,medium-elsereturnBinary-時間復雜度分析：第1步為合并排序，時間復雜度為O(nlogn)，2-5步為一個復雜度為n的循環(huán)，循環(huán)內(nèi)部執(zhí)行二分查找算法，復雜度為O(logn)，因此2-5步整體的時間復雜度為O(nlogn)，第6步復雜度為O(1)。因此，該O(nlogn)。A[x]，O(1)。kAA[1:n]，xAmx=A[m]，m=n/2+1，則xAxA[1]A[n]3A[n]A[1:m-1]A[1:m-1]3）x>=A[1]且x>=A[n]，例如A={2,3,4,5,6,1}，x=5，此時A中最大元素應(yīng)A[m:n]A[m:n]采用相同的方法進行求解。因為每次求x便將A分成了兩個子數(shù)組，所以至多求log(n)次x并進行比較，即可求出A中最大的元素。該算法的時間復雜度與二分查找法類似，為個數(shù)在數(shù)組C[n*m]n*mC[n*m],low=0,C[n*m]kIfIfreturnElseIfFindMink(C,low,q-x<-whileC[high]<-C[low]<-C[high]<-Returnhigh代表元素xpx，py輸出：若xpx,py;Ifreturn