如果您无法下载资料，请参考说明：
1、部分资料下载需要金币，请确保您的账户上有足够的金币
2、已购买过的文档，再次下载不重复扣费
3、资料包下载后请先用软件解压，在使用对应软件打开
2024/10/6ReviewoflastclassHowtodescribeanalgorithm?Howtodescribeanalgorithm?(II)Howtodescribeanalgorithm?(III)Howtodescribeanalgorithm?(IV)FundamentalsoftheAnalysisofAlgorithmEfficiency(I)GoalsofthislectureAnalysisofalgorithmsGoal:DeterminestheamountoftimethatanalgorithmneedstobeexecutedMethods:DeterminestheexactamountoftimethatanalgorithmneedstobeexecutedDeterminesthenumberofrepetitionsofalltheoperationsasafunctionofinputsizeandinputinstanceWhereNistheinputsize,Iistheinputinstance.OperationsSizeofInputExamplesTheoreticalanalysisoftimeefficiencyInputsizeandbasicoperationexamplesBestCaseAnalysisLeastamountofworktobedoneoverallofthepossibleinputwiththesamesizeWorstCaseAnalysis(mostimportant!)MostamountofworktobedoneoverallofthepossibleinputwiththesamesizeAverageCaseAnalysisTheamountofworkaveragedoverallofthepossibleinputsetswiththesamesizeNOTtheaverageofworstandbestcaseExample:SequentialsearchRateofGrowth(Important)RateofGrowthClassificationofGrowthAsymptoticNotation:O(mostimportant!)AsymptoticNotation:OAsymptoticNotation:AsymptoticNotation:SomepropertiesofasymptoticorderofgrowthAsymptoticNotation:AsymptoticNotation:OrdersofgrowthofsomeimportantfunctionsBasicasymptoticcomplexityclassesAsymptoticNotation:oAsymptoticNotationTheEnd
立即下载
