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

《数据结构与算法分析 2new.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Chapter2AlgorithmAnalysisAnalgorithmisaclearlyspecifiedsetofsimpleinstructionstobefollowedtosolveaproblem.Algorithmanalysisistheamountofcomputermemoryandtimeneededtorunaprogram(algorithm)Weusetwoapproachestodetermineit:performanceanalysisperformancemeasurementSpacecomple

2、xity:theamountofmemoryaprogramneedstoruntocompletionTimecomplexity:theamountoftimeaprogramneedstoruntocompletion2.1SpaceComplexity1)components:instructionspacedataspace(spaceneededforconstants,simplevariables,componentvariables)environmentstackspace(tosaveinformationneed

3、edtoresumeexecutionofpartiallycompletedfunctions)2.1SpaceComplexitytwoparts:afixedpart—includespaceforinstructions,simplevariables,fixed-sizecomponentvariables,constantsavariablepart—includespaceforcomponentvariables,dynamicalallocatedspace,recursionstackS(p)=c+Sp(instan

4、cecharacteristics)2.1SpaceComplexity2)example:SequentialSearchpublicstaticintSequentialSearch(int[]a,intx){inti;for(i=0;i

5、lexityRecursivecodetoadda[0:n-1]publicstaticfloatRsum(float[]a,intn){if(n>0)returnRsum(a,n-1)+a[n-1];return0;}2.1SpaceComplexityRecursionstackspace:formalparameters:a(2byte),n(2byte)returnaddress(2byte)Depthofrecursion:n+1SRsum(n)=6(n+1)2.2TimecomplexityThetimetakenbyapr

6、ogrampisT(p)T(p)=compiletime+runtimeThecompiletimedoesnotdependontheinstancecharacteristicsTheruntimeisdenotedbytp(instancecharacteristics)1)operationcountsidentifyoneormorekeyoperationsanddeterminethenumberoftimestheseareperformed2.2TimeComplexityExample1findingthelarge

7、stnumberina[0:n-1]publicstaticintMax(int[]a,intn){//locatethelargestelementina[0:n-1]intpos=0;for(inti=1;i

8、162125*25492.2TimeComplexitypublicstaticvoidSelectionSort(int[]a,intn){//sortthennumberina[0:n-1].for(i