算法與設計算法分析基礎整體框架

2023/4/241ReviewoflastclassHowtosolveaproblembycomputerThenotionofalgorithmActualproblemMathematicsmodelAlgorithmdesignandanalysisProgrammingResultanalysisInputoutputfinitenesseffectivenessdefinitenessAlgorithmdesignpattern2023/4/242Howtodescribeanalgorithm?NaturallanguageStep1Inputmandn.Step2Dividembynandassignthevalueoftheremaindertor.Step3Ifr=0,returnthevalueofnastheanswerandstop;otherwise,proceedtoStep4.Step4Assignthevalueofntomandthevalueofrton.Step5GotoStep2.Advantages:easyunderstandDisadvantages:existinherentambiguity2023/4/243Howtodescribeanalgorithm?(II)FlowchartStartr=0Inputmandnr=m%nm=nn=routputnStopAflowchartisamethodofexpressinganalgorithmbyacollectionofconnectedgeometricshapescontainingdescriptionsofthealgorithm’ssteps.Advantages:intuitiveDisadvantages:lackflexibility2023/4/244Howtodescribeanalgorithm?(III)ProgramminglanguageAdvantages:canrunoncomputerdirectlyDisadvantages:lackabstraction#include<iostream.h>intGCD(intm,intn){

intr=m%n;

while(r!=0) { m=n; n=r; r=m%n; }

returnn;}voidmain(void){ cout<<GCD(60,24)<<endl;}2023/4/245Howtodescribeanalgorithm?(IV)Pseudocode1r=m%n;2Whiler≠02.1m=n;2.2n=r;2.3r=m%n;3returnn;Advantages:moreprecisethannaturallanguageApseudocodeisamixtureofanaturallanguageandprogramminglanguage.Itusesthebasicgrammarofprogramminglanguage,buttheoperationinstructionscandesignedwithnaturallanguage.Disadvantages:notexistasingleformofpseudocode2023/4/246FundamentalsoftheAnalysisofAlgorithmEfficiency(I)Chapter21、Theframeworktoanalyzealgorithms

2、Best,worst,average-caseanalysis

3、Threeasymptoticnotations2023/4/247GoalsofthislectureAttheendofthislecture,youshouldbeabletoDescribehowtoanalyzeanalgorithmUnderstandwhatisabest-case,worse-caseandaverage-caseanalysisMasterthethreeasymptoticnotations,,O,rateofgrowth2023/4/248AnalysisofalgorithmsDefinition:

Algorithmanalysismeanstoevaluatethetwocomputerresources,timeandspace,whichneededbyanalgorithm.Lessresourcesanalgorithmneeds,moreefficiencyitis.

Issues:timeefficiencyDeterminestheamountoftimethatalgorithmneedstobeexecuted.spaceefficiencyDeterminestheamountofspacethatalgorithmneedstobeexecuted.Approaches:

theoreticalanalysisempiricalanalysis2023/4/249Goal:DeterminestheamountoftimethatanalgorithmneedstobeexecutedMethods:DeterminestheexactamountoftimethatanalgorithmneedstobeexecutedDeterminesthenumberofrepetitionsofalltheoperationsasafunctionofinputsizeandinputinstanceWhereNistheinputsize,Iistheinputinstance.Theoreticalanalysisoftimeefficiency2023/4/2410OperationsComparisonsEqual,greater,notequal,…LogicaloperationsAnd,or,xor,not,…ArithmeticoperationsAdditions:add,subtract,increment,decrementMultiplications:multiply,divide,modAssignmentoperationX=1Forconvenience,eachelementaryoperationisconsideredtouse1timeunit.2023/4/2411SizeofInputSortingandFindingproblems:numberofelementinthearrayortableGraphalgorithms:numberofverticesoredges,orsumofbothComputationalGeometry:usuallynumberofpoints,vertices,edges,linesegments,orpolygons.MatrixOperation:dimensionofmatrixNumbertheoryandcryptography:numberofbitsofinputnumber2023/4/2412Examplesxx+1for

j1to

n

doxx+1repeatT(N,I)=3nnadditions，2nassignmentsT(N,I)=21addition，1assignmentfor

i1to

n

do

for

j1to

n

do

xx+1

repeatrepeatT(n)=3n2+nn2additions，2n2+nassignments2023/4/2413TheoreticalanalysisoftimeefficiencyDeterminingthenumberofrepetitionsofthebasicoperationasafunctionofinputsizeandinputinstanceBasicoperation:theoperationthatcontributesmosttowardstherunningtimeofthealgorithm

T(N,I)≈copC(N,I)runningtimeexecutiontimeforbasicoperationNumberoftimesbasicoperationisexecutedinputsize,inputinstance2023/4/2414InputsizeandbasicoperationexamplesBasicoperationInputsizemeasureProblemVisitingavertexortraversinganedge#verticesand/oredgesTheshortestpathproblemMultiplicationoftwonumbersMatrixdimensionsortotalnumberofelementsMultiplicationoftwomatricesKeycomparisonNumberoflist’sitems,i.e.nSearchingforkeyinalistofnitems2023/4/2415BestCaseAnalysisLeastamountofworktobedoneoverallofthepossibleinputwiththesamesizeWorstCaseAnalysis(mostimportant!)MostamountofworktobedoneoverallofthepossibleinputwiththesamesizeBest-case,average-case,worst-case2023/4/2416AverageCaseAnalysisTheamountofworkaveragedoverallofthepossibleinputsetswiththesamesizeNOTtheaverageofworstandbestcaseBest-case,average-case,worst-case(II)2023/4/2417Example:SequentialsearchWorstcaseBestcaseAveragecase2023/4/2418RateofGrowth(Important)Therateofgrowthofafunctiondetermineshowfastthefunctionvalueincreaseswhentheinputincrease2023/4/2419RateofGrowthThefunctionx3growsfasterthanthefunctionx2IfalgorithmAdoesx3operationsonaninputofsizexandalgorithmBdoesx2operations,algorithmBismoreefficientBecauseoftherelativeratesofgrowthoffunctions,wewillconsiderthefunctions

x3+x2+xequivalenttox3(thereasonisthatwhenxislarge,thedifferencebetweenthemislittle,soweonlykeeptheitemthatgrowsfastestwhileomitothers)2023/4/2420ClassificationofGrowthBigOmega?(f):Theclassoffunctionsthatgrowatleastasfastasthefunctionf,andmaybefasterBigOhO(f):Theclassoffunctionsthatgrownofasterthanf,andmaybeslowerBigTheta(f)Theclassoffunctionsthatgrowatthesamerateasthefunctionf2023/4/2421AsymptoticNotation:O(mostimportant!)O-notation:asymptoticupperboundCallf(n)=O(g(n))ifthereexistpositiveconstantscandn0suchthat0f(n)cg(n)forallnn0.Or,if,thenf(n)=O(g(n))f(n)=2n3+3n-5

=O(n3)f(n)=2n3+3n-5

=

O(n4)Intheanalysisliterature,f(n)=

O(g(n))meansf(n)O

(g(n))Thinking:2n=O(2n+1)?2n+1=O(2n)?(logn)2=O(n)? (n+1)!=O(n!)2023/4/2422AsymptoticNotation:Onf(n)cg(n)n0f(n)=O(g(n))2023/4/2423AsymptoticNotation:-notation:asymptoticlowerboundCallf(n)=(g(n))ifthereexistpositiveconstantscandn0suchthat0cg(n)f(n)

forallnn0.or,if,thenf(n)=(g(n))f(n)=2n3+3n-5

=

(n3)f(n)=2n3+3n-5

=

(n2)Intheanalysisliterature,f(n)=

(g(n))meansf(n)

(g(n))2023/4/2424AsymptoticNotation:ncg(n)f(n)n0f(n)=(g(n))2023/4/2425Somepropertiesofasymptoticorderofgrowthf(n)O(f(n))

f(n)O(g(n))iffg(n)(f(n))

Iff

(n)O(g

(n))andg(n)O(h(n)),thenf(n)O(h(n))

Iff1(n)O(g1(n))andf2(n)O(g2(n)),thenf1(n)+

f2(n)O(max{g1(n),g2(n)})2023/4/2426AsymptoticNotation:-notation:

Callf(n)=(g(n))ifthereexistpositiveconstantsc1,c2,andn0suchthat0c1g(n)f(n)c2g(n)forallnn0.or,if,cisaconstantandc

>0,thenf(n)=(g(n))f(n)=2n3+3n-5

=(n3)f(n)=2n4+1=(n3)???2023/4/2427AsymptoticNotation:f(n)=(g(n))nf(n)c2g(n)n0c1g(n)2023/4/2428OrdersofgrowthofsomeimportantfunctionsAlllogarithmicfunctionslogan

belongtothesameclass

(logn)nomatterwhatthelogarithm’sbasea>1is

Allpolynomialsofthesamedegreekbelongtothesameclass:

aknk+ak-1nk-1+…+a0(nk)

Exponentialfunctionsanhavediffe