算法設(shè)計(jì)與分析課件：Lecture 01 Introduction

Lecture1

IntroductionOverview1.Introduction (a)WhatareAlgorithms? (b)DesignofAlgorithms. (c)AnalysisofAlgorithms.2.Complexity (a)Asymptoticanalysis,OandΘ. (b)Orderofgrowth.Whatarealgorithms?Analgorithmisawell-definedfinitesetofrulesthatspecifiesasequentialseriesofelementaryoperationstobeappliedtosomedatacalledtheinput,producingafterafiniteamountoftimesomedatacalledtheoutput.Analgorithmsolvessomecomputationalproblem.Algorithms(alongwithdatastructures)arethefundamental“buildingblocks”fromwhichprogramsareconstructed.Onlybyfullyunderstandingthemisitpossibletowriteveryeffectiveprograms.CharacteristicsofalgorithmsAllalgorithmsmustsatisfythefollowingcriteria: (1)Input:Therearezeroormorequantitiesthatareexternallysupplied. (2)Output:Atleastonequantityisproduced. (3)Definiteness（確定性）:Eachinstructionisclearandunambiguous. (4)Finiteness（有窮性）:Ifwetraceouttheinstructionsofanalgorithm,thenforallcases,thealgorithmterminatesafterfinitenumberofsteps. (5)Effectiveness（有效性）:Everyinstructionmustbebasicenoughtobecarriedout,inprinciple,byapersonusingonlypencilandpaper.AlgorithmdesignandanalysisAnalgorithmicsolutiontoacomputationalproblemwillusuallyinvolvedesigninganalgorithm,andthenanalysingitsperformance.DesignAgoodalgorithmdesignermusthaveathoroughbackgroundknowledgeofalgorithmictechniques,butespeciallysubstantialcreativityandimagination.AnalysisAgoodalgorithmanalystmustbeabletocarefullyestimateorcalculatetheresources(time,spaceorother)thatthealgorithmwillusewhenrunning.Thisrequireslogic,careandoftensomemathematicalability.Theaimofthiscourseistogiveyousufficientbackgroundtounderstandandappreciatetheissuesinvolvedinthedesignandanalysisofalgorithms.DesignandanalysisIndesigningandanalysinganalgorithmweshouldconsiderthefollowingquestions: 1.Whatistheproblemwehavetosolve? 2.Doesasolutionexist? 3.Canwefindasolution(algorithm),andistheremorethanonesolution? 4.Isthealgorithmcorrect? 5.Howefficientisthealgorithm?Algorithmdesignandanalysis--anexampleTheFibonaccisequenceisthesequenceofintegersstarting: 1,1,2,3,5,8,13,21,34,55,...Theformaldefinitionis: F1=F2=1andFn=Fn?1+Fn?2.PleasedeviseanalgorithmtocomputeFn.AnaiverecursivesolutionAnaivesolutionistosimplywritearecursivemethodthatdirectlymodelstheproblem.Isthisagoodalgorithm/programintermsofresourceusage?Timingitona(2005)iMacgivesthefollowingresults(thetimeisinsecondsandisforaloopcalculatingFn10000times).intfib(intn){

return

(n<

3

?

1

:fib(n-1)

+fib(n-2));}AnaiverecursivesolutionHowlongwillittaketocompute F30,F40orF50?Exercise:Showthenumberofmethodcallsmadetofib()is2Fn-1?1.AniterativealgorithmWfib(intn)

{

intf_2;

/*F(i+2)*/

intf_1=

1;

/*F(i+1)*/

intf_0=

1;

/*F(i)*/

for

(int

i

=

1;

i

<n;

i++)

{

/*F(i+2)=F(i+1)+F(i)*/f_2=f_1+f_0;

/*F(i)=F(i+1);F(i+1)=F(i+2)*/f_0=f_1;f_1=f_2;

}

returnf_0;}AmatrixalgorithmWehavethefollowingequation:UseMathematicalInduction: Basis:Forn=2, Inductivestep:Ifn=k,theequationholds,thenAmatrixalgorithm Bothsidesmultiplyby[1,1;1,0],weget Thus,theequationholdsforn=k+1.Usetheideaofdivide-and-conquerAlittlemore…GeneraltermformulaProveituseinduction.Hardtoimplement.EvaluatingalgorithmsCorrectness 1.Theoreticalcorrectness 2.NumericalstabilityEfficiency 1.Time 2.SpaceAnalgorithmisefficientifitusesasfewresourcesaspossible.Inmanysituationsthereisatrade-offbetweentimeandspace,inthatanalgorithmcanbemadefasterifitusesmorespaceorsmallerifittakeslonger.Althoughathoroughanalysisofanalgorithmshouldconsiderbothtimeandspace,timeisconsideredmoreimportant.NumericalstabilityYoucanbefairlycertainofexactresultsfromacomputerprogramprovidedallarithmeticisdonewiththeintegers

Z={...,?3,?2,?1,0,1,2,3,...}andyouguardcarefullyaboutanyoverflow.Howeverthesituationisentirelydifferentwhentheprobleminvolvesrealnumber,becausethereisnecessarilysomeround-offerrorwhenrealnumbersarestoredinacomputer.Afloatingpointrepresentationofanumberinbase"withprecisionpisarepresentationoftheform.Accumulationoferrors#include<stdio.h>intmain(){

doublet=

0.1;

for

(int

i

=

0;

i

<

20;

i++)

{

printf("%.16lf\n",t);t+=

0.1;

}

return

0;}MeasuringtimeHowshouldwemeasurethetimetakenbyanalgorithm?Wecandoitexperimentallybymeasuringthenumberofsecondsittakesforaprogramtorun—thisisoftencalledbenchmarkingandisoftenseeninpopularmagazines.Thiscanbeuseful,butdependsonmanyfactors:Themachineonwhichitisrunning.Thelanguageinwhichitiswritten.Theskilloftheprogrammer.Theinstanceonwhichtheprogramisbeingrun,bothintermsofsizeandwhichparticularinstanceitis.Soitisnotanindependentmeasureofthealgorithm,butratherameasureoftheimplementation,themachineandtheinstance.ComplexityThecomplexityofanalgorithmisa“device-independent”measureofhowmuchtimeitconsumes.Ratherthanexpressingthetimeconsumedinseconds,weattempttocounthowmany“elementaryoperations”thealgorithmperformswhenpresentedwithinstancesofdifferentsizes.Theresultisexpressedasafunction,givingthenumberofoperationsintermsofthesizeoftheinstance.Thismeasureisnotaspreciseasabenchmark,butmuchmoreusefulforansweringthekindofquestionsthatcommonlyarise:Iwanttosolveaproblemtwiceasbig.Howlongwillthattakeme?Wecanaffordtobuyamachinetwiceasfast?Whatsizeofproblemcanwesolveinthesametime?Theanswerstoquestionslikethisdependonthecomplexityofthealgorithm.DifferentinstancesofthesamesizeWehaveassumedthatthealgorithmtakesthesameamountoftimeoneveryinstanceofthesamesize.Butthisisalmostnevertrue,andsowemustdecidewhethertodobestcase,worstcaseoraveragecaseanalysis.Inbestcaseanalysisweconsiderthetimetakenbythealgorithmtobethetimeittakesonthebestinputofsizen.Inworstcaseanalysisweconsiderthetimetakenbythealgorithmtobethetimeittakesontheworstinputofsizen.Inaveragecaseanalysisweconsiderthetimetakenbythealgorithmtobetheaverageofthetimestakenoninputsofsizen.Anexample-InsertionsortLines2-7willbeexecutedntimes,lines4-5willbeexecuteduptojtimesforj=1ton.AsymptoticnotationsBig-Onotation:Itdefinesanasymptoticupperboundforafunctionf(n).

Definition:Afunctionf(n)issaidtobeO(g(n))ifthereareconstantscandn0suchthat

f(n)≤cg(n),?n≥n0.Big-Omeganotation():Itdefinesanasymptoticlowerboundforafunctionf(n).Big-Thetanotation:Itdefinesanasymptoticupperandlowerboundforafunctionf(n). Definition:Afunctionf(n)issaidtobe(g(n))ifthereareconstantsc1,c2andn0suchthat 0≤c1g(n)≤f(n)≤c2g(n),?n≥n0.Ifwesaythatf(n)=(n2)thenweareimplyingthatf(n)isapproximatelyproportionalton2forlargevaluesofn.Asymptoticnotationsf(n)=(

g(n))nn0c1g(n)c2g(n)f(n)Thereexistpositiveconstantsc1andc2suchthatthereisapositiveconstantn0suchthat…f(n)=O(

g(n))nn0f(n)cg(n)Thereexistpositiveconstantscsuchthatthereisapositiveconstantn0suchthat…f(n)=(

g(n))nn0cg(n)f(n)Thereexistpositiveconstantscsuchthatthereisapositiveconstantn0suchthat…OrderofgrowthAsymptoticnotations:,O,,o,.Theconstantcoefficient(s)areignored.Lowerorderitem(s)areignored,justkeepthehighestorderitem.Therateofgrowth,ortheorderofgrowth,possessesthehighestsignificance.Theinsertionsortrunsin(n2).f(n)=(g(n))actuallymeans：f(n)

(g(n))。Typicalorderofgrowth:O(1),O(logn),O(n),O(n),O(nlogn),O(n2),O(n3),O(2n),O(n!).What’sthecomplexityofeachFibalgorithm?ApproximationforfactorialsStirling’sapproximation

Arithmetic

operationO(f(n))+O(g(n))=

O(max{f(n),g(n)})；O(f(n))+O(g(n))=

O(f(n)+g(n))；O(f(n))*O(g(n))=

O(f(n)*g(n))；O(cf(n))=

O(f(n))；g(n)=O(f(n))O(f(n))+O(g(n))=

O(f(n))。Orderofgrowth2nn2nlognnlognfnAnasymptoticallybettersortingalgorithm:Merge-sortAnalysisoftheMerge-sortalgorithmDescribedbyrecursiveequationSupposeT(n)istherunningtimeonaproblemofsizen.T(n)=(1)ifnnc