资源描述
Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,Click to edit Master title style,2024/9/16,1,Review of last class,The framework of analyzing the time efficiency of an algorithm,The best-case, worse-case and average-case analysis,Rate of growth,and three asymptotic notations, ,O,2024/9/16,2,Fundamentals of the Analysis of Algorithm Efficiency,(II),Chapter 2,1,、,Formal definition of three asymptotic notations 2,、,Mathematical Background,3,、,Analysis of non-recursive algorithms,2024/9/16,3,Goals of this lecture,At the end of this lecture, you should,Master the three asymptotic notations, ,O,Be familial with the basic mathematical tools,Master the analysis of non-recursive algorithms,2024/9/16,4,Asymptotic Notation:,-notation: asymptotic lower bound,Call,f,(,n,) =,(,g,(,n,) if there exist positive constants,c,and,n,0,such that 0,cg,(,n,),f,(,n,),for all,n,n,0,.,f,(,n,) = 2,n,3,+3,n,-5,=,(,n,3,),f,(,n,) = 2,n,3,+3,n,-5,=,(,n,2,),In the analysis literature,f,(,n,),=,(,g,(,n,) means,f,(,n,),(,g,(,n,),2024/9/16,5,Asymptotic Notation:,n,cg,(,n,),f,(,n,),n,0,f,(,n,) =,(,g,(,n,),2024/9/16,6,Asymptotic Notation:,-notation:,Call,f,(,n,) =,(,g,(,n,) if there exist positive constants,c,1, c,2,and,n,0,such that,0,c,1,g,(,n,) ,f,(,n,),c,2,g,(,n,) for all,n,n,0,.,f,(,n,) = 2,n,3,+3,n,-5,= (,n,3,),f,(,n,) = 2,n,4,+1 = (,n,3,) ?,2024/9/16,7,Asymptotic Notation:,f,(,n,) =,(,g,(,n,),n,f,(,n,),c,2,g,(,n,),n,0,c,1,g,(,n,),2024/9/16,8,Useful properties of asymptotic notations,f,(,n,),O(,f,(,n,),f,(,n,),O(,g,(,n,) iff,g,(,n,),(,f,(n),If,f,(,n,),O(,g,(,n,) and,g,(,n,),O(,h,(,n,) ,then,f,(,n,),O(,h,(,n,),If,f,1,(,n,),O(,g,1,(,n,) and,f,2,(,n,),O(,g,2,(,n,) ,then,f,1,(,n,),+,f,2,(,n,),O(max,g,1,(,n,),g,2,(,n,),2024/9/16,9,Using Limits for Comparing Orders of Growth,A much more convenient method for comparing the orders of growth of two specific functions is based on computing the limit of the ratio of two functions:,The first two cases, say , mean that,f,(,n,),O,(,g,(,n,),The last two cases, say , mean that,f,(,n,), ,(,g,(,n,),The second cases, say , mean that,f,(,n,), ,(,g,(,n,),Compare the orders of growth of log,n,and,Compare the orders of growth of,n,! and 2,n,Compare the orders of growth of 1/2,n,(,n,-1) and,n,2,2024/9/16,10,Orders of growth of some important functions,All logarithmic functions log,a,n,belong to the same class,(,log,n,) no matter what the logarithms base,a, 1 is,All polynomials of the same degree,k,belong to the same class:,a,k,n,k,+,a,k,-1,n,k,-1,+ +,a,0, (,n,k,),Exponential functions,a,n,have different orders of growth for different,a,s,2024/9/16,11,Asymptotic Notation:,o,o,-notation,Call,f,(,n,) =,o,(,g,(,n,) if there exist positive constants,c,and,n,0,such that,f,(,n,),cg,(,n,) for all,n,n,0,.,Or, if , then,f,(,n,) =,o,(,g,(,n,),f,(,n,) = 2,n,3,+3,n,-5,=,o,(,n,4,),f,(,n,) =,o,(,g,(,n,),if and only if,f,(,n,) =,O,(,g,(,n,),but,g,(,n,) ,O,(,f,(,n,),n,log,n = o,(,n,2,) means that,n,log,n =,O,(,n,2,),but,n,2,O,(,n,log,n,),2024/9/16,12,Asymptotic Notation,Using the,o-,notation, we can concisely express the following hierarchy of complexity classes.,Polynomial complexity classes:,1, log,n,n,n,log,n,n,2,1),n,! = k,Basis:,Show formula is true when n = k,Inductive hypothesis:,Assume formula is true for an arbitrary n-1,Inductive Step:,Show that formula is then true for n,Example,Proof (1+x),n,1+nx for every real number x-1 and for every natural number n.,2024/9/16,17,Floor and ceiling functions,x,:,t,he floor of,x,is the largest integer, to,x,x,: t,he ceiling of,x,is the smallest integer to,x,Example:,3.5,= 3,-3.5,= -4,3.5,= 4,-3.5,= -3,Note:,-,x,= -,x,-,x,= -,x,x,/2,+,x,/2,=,x,log(n+1),=,logn,+1,Theorem:,Let,f,(,x,) be monotonically increasing function such that if,f,(,x,) is integer, then,x,is integer. Then,f,(,x,),=,f,(,x,),and,f,(,x,),=,f,(,x,),2024/9/16,18,Plan for Analysis of Nonrecursive Algorithms,Decide on a parameter indicating an inputs size.,Identify the algorithms basic operation.,Check whether the number of times the basic op. is executed may vary on different inputs of the same size. (If it may, the worst, average, and best cases must be investigated separately.),Set up a sum expressing the number of times the algorithms basic operation is executed.,Using standard formulas and rules of sum manipulation, either find a closed form formula for the count or, at very least, establish its order of growth.,2024/9/16,19,Summations,A summation is a compact way to express the sum of a series of values,The sum of the numbers from 1 to 7 would be written:,There are closed forms for many summations given,in the,appendix A and next slide, please remember them.,2024/9/16,20,Useful Summation Formulas,2024/9/16,21,Useful Formulas,2024/9/16,22,Example 1: Maximum element,Input size:,Basic operation:,Best, worst, average case:,Summation:,n,Comparison,no,2024/9/16,23,Example 2: Element uniqueness problem,Input size:,Basic operation:,Best, worst, average case:,Summation: C,worst,=,n,Comparison,yes,2024/9/16,24,Example 3: Matrix multiplication,Input size:,Basic operation:,Best, worst, average case:,Summation:,n,Multiplication,no,2024/9/16,25,Example 4: Counting binary digits,Input size:,Basic operation:,Best, worst, average case:,Summation:,n,Comparison,no,About log,n,2024/9/16,26,The End,2024/9/16,27,Assignment,Exercises:,No 2,3,5,7 of exercises 2.2,No 4,5 of exercises 2.3,2024/9/16,28,
展开阅读全文