算法设计与分析教学课件2.pdf

AnalysisAnalysisAnalysisAnalysis andandandand DesignDesignDesignDesign ofofofof AlgorithmsAlgorithmsAlgorithmsAlgorithms Chapter 2: Fundamentals of the Analysis Transform Coding ofof AlgorithmAlgorithm EfficiencyEfficiency School of Software Engineering ©School of Software Engineering © Yanling XuYanling Xu FundamentalsFundamentalsFundamentalsFundamentals ofofofof thethethethe AnalysisAnalysisAnalysisAnalysis ofofofof AlgorithmAlgorithmAlgorithmAlgorithm EfficiencyEfficiencyEfficiencyEfficiency Algorithm analysis framework Asymptotic notations AnalysisAnalysis ofof nonnon-recursiverecursive algorithmsalgorithms Analysis of recursive algorithms Analysis of recursive algorithms 2 AnalysisAnalysisAnalysisAnalysis ofofofof AlgorithmsAlgorithmsAlgorithmsAlgorithms Analysis of algorithms means to investigate an allgorithithm’’s effifficiiency withith respectt tto resources: running time and memory space. withith respectt tto iinputt siize, iinputt ttype, andd allgorithithm function C=F(N, I, A) Ti ffi i T(N I) Time efficiency T(N, I): how fast an algorithm runs. Space efficiency S(N , I): the space an algorithm requires. 3 AnalysisAnalysisAnalysisAnalysis ofofofof AlgorithmsAlgorithmsAlgorithmsAlgorithms Time efficiency T(N, I): time consumed for an algorithm running on an computer Element operations O O O Element operations O , O …, O 1 2, k,