ch02 algorithm analysis

《ch02 algorithm analysis》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、CHAPTER2ALGORITHMANALYSIS【Definition】Analgorithmisafinitesetofinstructionsthat,iffollowed,accomplishesaparticulartask.Inaddition,allalgorithmsmustsatisfythefollowingcriteria:(1)InputTherearezeroormorequantitiesthatareexternallysupplied.(2)OutputAtleastonequantityisproduced.(3)DefinitenessEachinstr

2、uctionisclearandunambiguous.(4)FinitenessIfwetraceouttheinstructionsofanalgorithm,thenforallcases,thealgorithmterminatesafterfinitenumberofsteps.(5)EffectivenessEveryinstructionmustbebasicenoughtobecarriedout,inprinciple,byapersonusingonlypencilandpaper.Itisnotenoughthateachoperationbedefiniteasin

3、(3);italsomustbefeasible.Note:Aprogramiswritteninsomeprogramminglanguage,anddoesnothavetobefinite(e.g.anoperationsystem).Analgorithmcanbedescribedbyhumanlanguages,flowcharts,someprogramminglanguages,orpseudo-code.〖Example〗SelectionSort:Sortasetofn1integersinincreasingorder.Fromthoseintegersthatar

4、ecurrentlyunsorted,findthesmallestandplaceitnextinthesortedlist.Whereandhowaretheystored?Where?for(i=0;i

5、AnalyzeMachine&compiler-dependentruntimes.Time&spacecomplexities:machine&compiler-independent.Assumptions:instructionsareexecutedsequentiallyeachinstructionissimple,andtakesexactlyonetimeunitintegersizeisfixedandwehaveinfinitememoryTypicallythefollowingtwofunctionsareanalyzed:Tavg(N)&Tworst(N

6、)--theaverageandworstcasetimecomplexities,respectively,asfunctionsofinputsizeN.Ifthereismorethanoneinput,thesefunctionsmayhavemorethanoneargument.§1WhattoAnalyze〖Example〗Matrixadditionvoidadd(inta[][MAX_SIZE],intb[][MAX_SIZE],intc[][MAX_SIZE],introws,intcols){inti,j;for(i=0;i

7、ls;j++)c[i][j]=a[i][j]+b[i][j];}/*rows+1*//*rows(cols+1)*//*rowscols*/T(rows,cols)=2rowscols+2rows+1Q:Whatshallwedoifrows>>cols?A:Exchangerowsandcols.〖Example〗Iterativefunctionforsummingalistofnumbersfloatsum(f