计算机算法分析设计复习题（computer algorithm analysis and design review）

《计算机算法分析设计复习题（computer algorithm analysis and design review）》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算机算法分析设计复习题（Computeralgorithmanalysisanddesignreview）Chapter1algorithmoverview1,thealgorithmmusthavefourproperties:Input:havingzeroormorequantitiessuppliedbytheoutsideasinputtothealgorithmOutput:thealgorithmproducesatleastonequantityasoutputDeterminis

2、tic:eachinstructionthatmakesupthealgorithmisclearandunambiguousFinite:aftertheimplementationofapoorstep,thealgorithmterminates(theprogramcannotsatisfythisproperty,suchastheoperatingsystem,Infiniteloop2.Writeoutthemathematicalexpressionoftheasymptoticbe

3、haviorofthealgorithmcomplexity:(abletowriteupperorderfunctions)suchas:3,thecomplexityofthealgorithmisdividedinto:timecomplexityrequirestime,theamountofresources;spacecomplexityrequirestheamountofspaceresources4,thespacerequiredbytheprogramSpatialspaceS

4、paceconsistsmainlyofinstructionspaceInstructionspaceInstructionspace,,,DataspaceDataspaceDataspace,,,EnvironmentEnvironmentenvironmentEnvironmentstackspaceStackspaceconstitutesastackspaceStackspacestructure:5.Analyzethetimecomplexityoftheprogramsegment

5、BubbleonceA,templateVoid,Bubble(T,a[],int,n){//calculatethemaximumelementinthea[0:n-1]shifttotherightthroughthebubbleFor(int,I,=1,ia[i+1])swap(a[i],a[i+1]);}B,templateVoid,BubbleSort(T,a[],int,n){//calculationina[0:n-1]

6、nelementsthroughthebubblesortFor(int,I,=n,i>1;i--)Bubble(a,I);}Thesecondchapterisrecursionanddivideandconquerstrategy1.Recursiveconcepts(recursivealgorithmscanbewrittenaccordingtorecursiveformulas)suchas:Recursivefunctionsareasfollows:A,int,Factorial(i

7、nt,n){If(n==0)return1;Returnn*Factorial(n-1);}B,Recursiveconcept:analgorithmthatcallsitselfdirectlyorindirectly,knownasarecursivealgorithm;afunctionthatdefinesitselfFunctionsarecalledrecursivefunctionsRecursivedisadvantage:timeandspaceadvantages:easyto

8、understandRecursivesummaryAdvantages:clearstructure,readability,andeasytousemathematicalinductiontoprovethecorrectnessofthealgorithm,soitistosetthecalculationThedebuggingprocessisveryconvenient.Disadvantages:therecursivealgorithmislesse