計算思維-課件-2lecture

計算機算法的若干基本要素陶先平算法的正確性是算法設(shè)計的第一保障要求一個插入排序方法插入法：在“插入每張牌前，手上的牌都是已經(jīng)排好序的”范例總是已經(jīng)排好序的片段總是已經(jīng)排好序的片段偽代碼循環(huán)不變量如何利用循環(huán)不變量證明算法的部分正確性用哪些數(shù)值來標定算法的性能？時間性能（時間復(fù)雜度）算法在給定一個輸入的情況下，要執(zhí)行多少條指令沒錯，數(shù)數(shù)字！數(shù)數(shù)字！性能評估函數(shù)BestcaseWorstcase如何評估不同的算法的性能差異？函數(shù)增長N(數(shù)據(jù)集規(guī)模)T(n)(算法執(zhí)行步數(shù))S(n)(算法執(zhí)行步數(shù))105501250506375078125010050500012500000兩個算法執(zhí)行步數(shù)隨著數(shù)據(jù)規(guī)模的變化而變化不同的算法，變化的“劇烈程度”不同引入一個數(shù)學(xué)工具來刻畫這種變化并嘗試判斷其不同函數(shù)的增長定義

函數(shù)f:N->N：數(shù)據(jù)規(guī)模->算法執(zhí)行步驟數(shù)針對上述兩個算法：fT(n)=n3/2+n2/2foralgorithmTfs(n)=n4/8foralgorithmS函數(shù)的增長速度給定f:N→R+,g:N→R+,如果存在常數(shù)cR+

和kN

使得對于所有大于等于k的n，都有f(n)C×g(n)我們稱：fisO(g)f

增長速度不高于g實際上：可以做如下判斷：函數(shù)

f

是Ο(g)iflimn→[f(n)/g(n)]=c<ifthereexistsconstantscR+andkNsuchthatforalln,f(n)cg(n)例如:letf(n)=n2,g(n)=nlgn，則:f不是Ο(g),因為limn→[f(n)/g(n)]=limn→[n2/nlgn]=limn→[n/lgn]=limn→[1/(1/nln2)]=g

是Ο(f),因為limn→[g(n)/f(n)]=0再例：letf(n)=n2,g(n)=7n2+9n-1limn→[f(n)/g(n)]=limn→[n2/(7n2+9n-1)]=1/7所以：f是Ο(g)limn→[g(n)/f(n)]=limn→[(7n2+9n-1)/n2]=7所以：g是Ο(f)我們稱：f和g長得一樣快(同階)其實：針對類似于T(n)=an2+bn+c的性能函數(shù)我們總是忽略bn+c他們的重要性在“增長”上影響力較小我們還可以忽略a他們的重要性在“增長”上影響力也較小因此：T(n)所代表的算法是O(n2)的一個和數(shù)據(jù)組織有關(guān)的優(yōu)化案例在一個無序的數(shù)據(jù)列表（比如無序的電話號碼本）中搜索Casy的電話號碼index=0；for(index=0,index<totalPhonenumber,index++){ IftelephoneList[index].name==“Casy”then returntelephoneList[index].no;}returnnull;如果數(shù)據(jù)是有序組織的呢？數(shù)據(jù)的有效組織對算法的優(yōu)化也是至關(guān)重要的！數(shù)據(jù)的組織和結(jié)構(gòu)涉及到哪些內(nèi)容？數(shù)據(jù)自身的邏輯模型按照字母序?qū)﹄娫捥柎a的戶主姓名進行排序按照學(xué)號順序?qū)W(xué)籍表數(shù)據(jù)進行排序……數(shù)據(jù)在計算機中的存儲模型數(shù)組方式棧的方式先進先出表的方式……結(jié)論算法的優(yōu)化是設(shè)計每個算法的必要考慮因素算法本身的優(yōu)化設(shè)計數(shù)據(jù)組織導(dǎo)致的優(yōu)化算法應(yīng)該進行數(shù)值分析以確定他們的性能算法時間性能評估函數(shù)可以通過算法的評估函數(shù)增長速度的比較來比較算法的優(yōu)劣作業(yè)Considerthefollowingsalarycomputationproblem.TheinputconsistsofanumberN,alist,BT(1),...,BT(N),ofbefore-taxsalaries,andtwotaxrates,RhforsalariesthatarelargerthanM,andRlforsalariesthatarenolargerthanM.HereRhandRlarepositivefractions,i.e.,0<Rh,Rl<1.Itisrequiredtocomputealist,AT(1),...,AT(N),ofafter-taxsalaries,andtwosums,ThandTl,containingthetotaltaxespaidaccordingtothetworates,respectively.Hereisasolutiontotheproblem.Itcalculatestheafter-taxsalariesfirstandthenthetaxtotals:forIfrom1toNdothefollowing: ifBT(I)>MthenAT(I)←BT(I)×(1?Rh); otherwiseAT(I)←BT(I)×(1?Rl);Th←0;Tl←0;forIfrom1toNdothefollowing: ifBT(I)>MthenTh←Th+BT(I)×Rh; otherwiseTl←Tl+BT(I)×Rl.(a)trytoprovethepartialcorrectnessofthealgorithm.(b)Suggestaseriesoftransformationsthatwillmaketheprogramasefficientaspossible,byminimizingboththenumberofarithmeticaloperationsandthenumberofcomparisons.Estimatetheimprovementtothesecomplexitymeasuresthatisgainedbyeachofyourtransformations.(c)Howwouldyoufurtherimprovetheprogram,ifyouareguaranteedthatnobefore-taxsala