算法与设计算法分析基础-整体框架

2026/9/181ReviewoflastclassHowtosolveaproblembycomputerThenotionofalgorithmActualproblemMathematicsmodelAlgorithmdesignandanalysisProgrammingResultanalysisInputoutputfinitenesseffectivenessdefinitenessAlgorithmdesignpattern2026/9/182Howtodescribeanalgorithm?NaturallanguageStep1Inputmandn.Step2Dividembynandassignthevalueoftheremaindertor.Step3Ifr=0,returnthevalueofnastheanswerandstop;otherwise,proceedtoStep4.Step4Assignthevalueofntomandthevalueofrton.Step5GotoStep2.Advantages:easyunderstandDisadvantages:existinherentambiguity2026/9/183Howtodescribeanalgorithm?(II)FlowchartStartr=0Inputmandnr=m%nm=nn=routputnStopAflowchartisamethodofexpressinganalgorithmbyacollectionofconnectedgeometricshapescontainingdescriptionsofthealgorithm’ssteps.Advantages:intuitiveDisadvantages:lackflexibility2026/9/184Howtodescribeanalgorithm?(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;}2026/9/185Howtodescribeanalgorithm?(IV)Pseudocode1r=m%n;2Whiler≠02.1m=n;2.2n=r;2.3r=m%n;3returnn;Advantages:moreprecisethannaturallanguageApseudocodeisamixtureofanaturallanguageandprogramminglanguage.Itusesthebasicgrammarofprogramminglanguage,buttheoperationinstructionscandesignedwithnaturallanguage.Disadvantages:notexistasingleformofpseudocode2026/9/186FundamentalsoftheAnalysisofAlgorithmEfficiency(I)Chapter21、Theframeworktoanalyzealgorithms

2、Best,worst,average-caseanalysis

3、Threeasymptoticnotations2026/9/187GoalsofthislectureAttheendofthislecture,youshouldbeabletoDescribehowtoanalyzeanalgorithmUnderstandwhatisabest-case,worse-caseandaverage-caseanalysisMasterthethreeasymptoticnotations,,O,rateofgrowth2026/9/188AnalysisofalgorithmsDefinition:

Algorithmanalysismeanstoevaluatethetwocomputerresources,timeandspace,whichneededbyanalgorithm.Lessresourcesanalgorithmneeds,moreefficiencyitis.

Issues:timeefficiencyDeterminestheamountoftimethatalgorithmneedstobeexecuted.spaceefficiencyDeterminestheamountofspacethatalgorithmneedstobeexecuted.Approaches:

theoreticalanalysisempiricalanalysis2026/9/189Goal:DeterminestheamountoftimethatanalgorithmneedstobeexecutedMethods:DeterminestheexactamountoftimethatanalgorithmneedstobeexecutedDeterminesthenumberofrepetitionsofalltheoperationsasafunctionofinputsizeandinputinstanceWhereNistheinputsize,Iistheinputinstance.Theoreticalanalysisoftimeefficiency2026/9/1810OperationsComparisonsEqual,greater,notequal,…LogicaloperationsAnd,or,xor,not,…ArithmeticoperationsAdditions:add,subtract,increment,decrementMultiplications:multiply,divide,modAssignmentoperationX=1Forconvenience,eachelementaryoperationisconsideredtouse1timeunit.2026/9/1811SizeofInputSortingandFindingproblems:numberofelementinthearrayortableGraphalgorithms:numberofverticesoredges,orsumofbothComputationalGeometry:usuallynumberofpoints,vertices,edges,linesegments,orpolygons.MatrixOperation:dimensionofmatrixNumbertheoryandcryptography:numberofbitsofinputnumber2026/9/1812Examplesx

x+1for

j1to

n

dox

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

i1to

n

do

for

j1to

n

do

x

x+1

repeatrepeatT(n)=3n2+nn2additions，2n2+nassignments2026/9/1813TheoreticalanalysisoftimeefficiencyDeterminingthenumberofrepetitionsofthebasicoperationasafunctionofinputsizeandinputinstanceBasicoperation:theoperationthatcontributesmosttowardstherunningtimeofthealgorithm

T(N,I)≈copC(N,I)runningtimeexecutiontimeforbasicoperationNumberoftimesbasicoperationisexecutedinputsize,inputinstance2026/9/1814InputsizeandbasicoperationexamplesBasicoperationInputsizemeasureProblemVisitingavertexortraversinganedge#verticesand/oredgesTheshortestpathproblemMultiplicationoftwonumbersMatrixdimensionsortotalnumberofelementsMultiplicationoftwomatricesKeycomparisonNumberoflist’sitems,i.e.nSearchingforkeyinalistofnitems2026/9/1815BestCaseAnalysisLeastamountofworktobedoneoverallofthepossibleinputwiththesamesizeWorstCaseAnalysis(mostimportant!)MostamountofworktobedoneoverallofthepossibleinputwiththesamesizeBest-case,average-case,worst-case2026/9/1816AverageCaseAnalysisTheamountofworkaveragedoverallofthepossibleinputsetswiththesamesizeNOTtheaverageofworstandbestcaseBest-case,average-case,worst-case(II)2026/9/1817Example:SequentialsearchWorstcaseBestcaseAveragecase2026/9/1818RateofGrowth(Important)Therateofgrowthofafunctiondetermineshowfastthefunctionvalueincreaseswhentheinputincrease2026/9/1819RateofGrowthThefunctionx3growsfasterthanthefunctionx2IfalgorithmAdoesx3operationsonaninputofsizexandalgorithmBdoesx2operations,algorithmBismoreefficientBecauseoftherelativeratesofgrowthoffunctions,wewillconsiderthefunctions

x3+x2+xequivalenttox3(thereasonisthatwhenxislarge,thedifferencebetweenthemislittle,soweonlykeeptheitemthatgrowsfastestwhileomitothers)2026/9/1820ClassificationofGrowthBigOmegaΩ(f):Theclassoffunctionsthatgrowatleastasfastasthefunctionf,andmaybefasterBigOhO(f):Theclassoffunctionsthatgrownofasterthanf,andmaybeslowerBigTheta

(f)Theclassoffunctionsthatgrowatthesamerateasthefunctionf2026/9/1821AsymptoticNotation:O(mostimportant!)O-notation:asymptoticupperboundCallf(n)=O(g(n))ifthereexistpositiveconstantscandn0suchthat0

f(n)

cg(n)foralln

n0.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!)2026/9/1822AsymptoticNotation:Onf(n)cg(n)n0f(n)=O(g(n))2026/9/1823AsymptoticNotation:

-notation:asymptoticlowerboundCallf(n)=

(g(n))ifthereexistpositiveconstantscandn0suchthat0

cg(n)

f(n)

foralln

n0.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))2026/9/1824AsymptoticNotation:

ncg(n)f(n)n0f(n)=

(g(n))2026/9/1825Somepropertiesofasymptoticorderofgrowthf(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)})2026/9/1826AsymptoticNotation:

-notation:

Callf(n)=

(g(n))ifthereexistpositiveconstantsc1,c2,andn0suchthat0

c1g(n)f(n)

c2g(n)foralln

n0.or,if,cisaconstantandc

>0,thenf(n)=

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

=(n3)f(n)=2n4+1=(n3)???2026/9/1827AsymptoticNotation:

f(n)=

(g(n))nf(n)c2g(n)n0c1g(n)2026/9/1828OrdersofgrowthofsomeimportantfunctionsAlllogarithmicfunctionslogan

belongtothesameclass

(logn)nomatterwhatthelogarithm’sbasea>1is

Allpolynomialsofthesamedegreekbelongtothesameclass:

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

Exponentialfunctionsanhaved