Ch2.1-2 Algorithm Analysis

《Ch2.1-2 Algorithm Analysis》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

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

2、sEachinstructionisclearandunambiguous.(4)FinitenessIfwetraceouttheinstructionsofanalgorithm,thenforallcases,thealgorithmterminatesafterfinitenumberofsteps.(5)EffectivenessEveryinstructionmustbebasicenoughtobecarriedout,inprinciple,byapersonusingonlypencilandpaper.Itisnotenoughthateachope

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

4、asingorder.Fromthoseintegersthatarecurrentlyunsorted,findthesmallestandplaceitnextinthesortedlist.Whereandhowfor(i=0;i

5、estinteger+Interchangeitwithlist[i].2/15§1WhattoAnalyzeMachine&compiler-dependentruntimes.Time&spacecomplexities:machine&compiler-independent.•Assumptions:instructionsareexecutedsequentiallyeachinstructionissimple,andtakesexactlyonetimeunitintegersizeisfixedandwehaveinfinitememory•T

6、ypicallythefollowingtwofunctionsareanalyzed:T(N)&T(N)--theaverageandworstcasetimeavgworstcomplexities,respectively,asfunctionsofinputsizeN.Ifthereismorethanoneinput,thesefunctionsmayhavemorethanoneargument.3/15§1WhattoAnalyze〖Example〗Matrixadditionvoidadd(inta[][MAX_SIZE],intb[][MAX_SIZE

7、],intc[][MAX_SIZE],Q:WhatshallwedoA:Exchangeintrows,intcols)ifrowsrows>>colsandcols.?{inti,j;for(i=0;i