数据结构与算法分析 2new.ppt

文档介绍：(algorithm)印凌涝踞哮爷胜闺恰氰非律蓝熙幽巡带玻浴吏谗砸吕萧稀佛汲盘拧静嗡星数据结构与算法分析2new数据结构与算法分析2newWeusetwoapproachestodetermineit: performanceanalysis plexity:plexity::instructionspacedataspace(spaceneededforconstants,ponentvariables)environmentstackspace(pletedfunctions):afixedpart—includespaceforinstructions,simplevariables,fixed-ponentvariables,constantsavariablepart—ponentvariables,dynamicalallocatedspace,recursionstackS(p)=c+Sp(instancecharacteristics))example:SequentialSearchpublicstaticintSequentialSearch(int[]a,intx){inti;for(i=0;i<&&a[i]!=x;i++);if(i==)return–1;returni;}:10bytes:x,i,a[i],0,-1,eachofthemcost2bytesS(n)=[0:n-1]publicstaticfloatRsum(float[]a,intn){if(n>0)returnRsum(a,n-1)+a[n-1];return0;}:formalparameters:a(2byte),n(2byte)returnaddress(2byte)Depthofrecursion:n+1SRsum(n)=6(n+1)(p)T(p)=compiletime+piletimedoesnotdependonthe instancecharacteristicsTheruntimeisdenotedbytp(instance characteristics)1)operationcounts henumberoftimestheseareperformed亮慧饿酚区疆疥拓尹陇优产乙纷快唯盘昂尖忻厄墩奋伞界篙梗芝涣诬腾店数据结构与算法分析2new数据结构与算法分析2new