欢迎来到天天文库
浏览记录
ID:48750175
大小:621.00 KB
页数:46页
时间:2020-01-26
《数据结构与算法分析 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;i5、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.2TimecomplexityThetimetakenbyapr6、ogrampisT(p)T(p)=compiletime+runtimeThecompiletimedoesnotdependontheinstancecharacteristicsTheruntimeisdenotedbytp(instancecharacteristics)1)operationcountsidentifyoneormorekeyoperationsanddeterminethenumberoftimestheseareperformed2.2TimeComplexityExample1findingthelarge7、stnumberina[0:n-1]publicstaticintMax(int[]a,intn){//locatethelargestelementina[0:n-1]intpos=0;for(inti=1;i8、162125*25492.2TimeComplexitypublicstaticvoidSelectionSort(int[]a,intn){//sortthennumberina[0:n-1].for(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;i8、162125*25492.2TimeComplexitypublicstaticvoidSelectionSort(int[]a,intn){//sortthennumberina[0:n-1].for(i
8、162125*25492.2TimeComplexitypublicstaticvoidSelectionSort(int[]a,intn){//sortthennumberina[0:n-1].for(i
此文档下载收益归作者所有