欢迎来到天天文库
浏览记录
ID:39715548
大小:177.59 KB
页数:13页
时间:2019-07-09
《lecture2 Complexity Analysis》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、Whatisanalgorithm?CS122AlgorithmsandDataStructuresIdeasbehindcomputerprogramsSolvesageneral,well-specifiedproblemStaysthesamenomatter–WhichkindofhardwareitisrunningonMW11:00am-12:15pm,MSEC101–WhichprogramminglanguageitiswritteninInstructor:XiaoQinSpecifies–Theset
2、ofinstances(input)Lecture2:ComplexityAnalysis–ThedesiredpropertiesoftheoutputExpressingAlgorithmsImportantPropertiesofAlgorithmsCorrectEnglishdescription –alwaysreturnsthedesiredoutputforall legalinstancesoftheproblem.Effici
3、entPseudocode–Measuredintermsoftimeorspace–TimetendstobemoreimportantHigh-levelprogramming–Therunningtimeanalysisallowsustoimproveouralgorithmslanguage1PseudocodeAnalysisofAlgorithmsAshorthandforspecifyingalgorithmsWhyanalyzealgorithms?Leavesouttheimplementation
4、details–evaluatealgorithmperformanceFocusontheessenceofthealgorithm–comparedifferentalgorithmsAlgorithmArrayMax(A,n)Analyzewhataboutthem?Input:AnarrayAstoringn>=1integersOutput:ThemaximumelementinA.–runningtime,memoryusagecurrentMaxA[0]–worst-caseand“typical”casefo
5、ri1ton-1doifcurrentMax6、ondefinedbythemaximumnumberofstepstakenonanyinstanceofsizenThemajorityofalgorithmsvariesitsnumberofstepsbasedonthesizeofinstanceBestCaseComplexity:–thefunctiondefinedbytheminimumnumberofTheefficiencyofanalgorithmisalwaysstatedstepstakenonanyinstanceofsizenasafunct7、ionoftheproblemsizeAverageCaseComplexity:–WegenerallyusethevariableNtorepresenttheproblemsize–thefunctiondefinedbytheaveragenumberofstepstakenonanyinstanceofsizen2Best,Worst,andAverageCaseDoingtheAnalysisComplexityIt’shardtoestimatetherunningtimeexactly 8、–Bestcasedependsontheinput–Averagecaseisdifficulttocompute–Soweusuallyfocusonworstcaseanalysis
6、ondefinedbythemaximumnumberofstepstakenonanyinstanceofsizenThemajorityofalgorithmsvariesitsnumberofstepsbasedonthesizeofinstanceBestCaseComplexity:–thefunctiondefinedbytheminimumnumberofTheefficiencyofanalgorithmisalwaysstatedstepstakenonanyinstanceofsizenasafunct
7、ionoftheproblemsizeAverageCaseComplexity:–WegenerallyusethevariableNtorepresenttheproblemsize–thefunctiondefinedbytheaveragenumberofstepstakenonanyinstanceofsizen2Best,Worst,andAverageCaseDoingtheAnalysisComplexityIt’shardtoestimatetherunningtimeexactly
8、–Bestcasedependsontheinput–Averagecaseisdifficulttocompute–Soweusuallyfocusonworstcaseanalysis
此文档下载收益归作者所有