计算机算法导论_第2章

《计算机算法导论_第2章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、IntroductiontoAlgorithms计算机算法导论2007~2008年第一学期Quiz(10minutes)QuestionSupposewearecomparingimplementationsofinsertionsortandmergesortonthesamemachine.Forinputsofsizen,insertionsortrunsin8n2steps,whilemergesortrunsin64nlgnsteps.Forwhichvaluesofndoesinsertio

2、nsortbeatmergesort?Whatisthesmallestvalueofnsuchthatanalgorithmwhoserunningtimeis100n2runsfasterthananalgorithmwhoserunningtimeis2nonthesamemachine?2、GettingStartedQuestionIntroducingtheinsertionsortalgorithmtosolvethesolvingproblemAnalyzingitsrunningtim

3、eDesigningthealgorithmbythedivide-and-conquerapproach2.1、InsertionsortProblemInput:sequenceofnumbers.Output:permutationsuchthata'1≤a'2≤…≤a'n.Example:Input:824936Output:234689PseudocodeDifferencebetweenpseudocodeandrealcodePseud

4、ocodeismoreclearandconciseSometimes,inEnglishPseudocodeisnottypicallyconcernedwithissueofsoftwareengineeringPseudocodeconventionsIndentationindicatesblockstructureTheloopingconstructswhile,forandrepeatandtheconditionalconstructsif,thenandelsehaveinterpre

5、tationssimilartothoseinPascalThe“”indicatesacommentAmultipleassignmentVariblesarelocaltothegivenprocedureA[1..j]Field[objects]indicatescompounddata,Avariablerepresentinganarrayorobjectistreatedasapointer,andNILpointerParametersarepassedtoaprocedurebyvalu

6、eThebooleanoperatorsisshortcircuitingPseudcode2.1、Insertionsort1.1、AlgorithmsCorrectandincorrectalgorthmsThespecificationofanalgorthmInenglishAcomputerprogramAharewaredesignLoopinvariantsInitialization:ItistruepriortothefirstiterationoftheloopMaintenance

7、:Ifitistruebeforeaniteration,itremainstruebeforethenextiterationTermination:Whentheloopterminates,theinvariantcanhelpsshowthatthealgorithmiscorrectThecorrectnessofinsertionsortInitialization:Theloopinvariantholdsbeforethefirstloopiteration,j=2.Maintenanc

8、e:Eachiterationmaintainstheloopinvariant.Termination:Whentheloopterminates,theentirearrayissorted,whichmeansthatthealgorithmiscorrect2.2、AnalyzingalgorithmsAnalyzingalgorithmsAnalyzingalgorithmsmeanspredictingtheresourcest