《算法课件全121301ADA03算法分析基础－递归与非递归算法的分析方法》由会员分享，可在线阅读，更多相关《算法课件全121301ADA03算法分析基础－递归与非递归算法的分析方法（25页珍藏版）》请在金锄头文库上搜索。
1、2019/6/21,2,2012-2013-01Design and Analysis of Algorithm SCUN,Review of last class,Methods for describing algorithm The framework for analyzing the time efficiency of an algorithm The best-case, worst-case and average-case analysis Rate of growth and two asymptotic notations , O,Fundamentals of the
2、Analysis of Algorithm Efficiency (II),Chapter 2,1、 Formal definition of asymptotic notations 2、 Mathematical Background 3、 Analysis of non-recursive algorithms,2019/6/21,4,2012-2013-01Design and Analysis of Algorithm SCUN,Goals of this lecture,At the end of this lecture, you should Master asymptotic
3、 notations Be familial with the basic mathematical tools Master the analysis of non-recursive algorithms,2019/6/21,5,2012-2013-01Design and Analysis of Algorithm SCUN,Asymptotic Notation: ,-notation: Call f(n) = (g(n) if there exist positive constants c1, c2, and n0 such that 0 c1g(n) f(n) c2g(n) fo
4、r all n n0. f(n) = 2n3+3n-5 = (n3) f(n) = 2n4+1 = (n3) ?,2019/6/21,6,2012-2013-01Design and Analysis of Algorithm SCUN,Asymptotic Notation: ,f(n) = (g(n),n,f(n),c2g(n),n0,c1g(n),2019/6/21,7,2012-2013-01Design and Analysis of Algorithm SCUN,Using Limits for Comparing Orders of Growth,A much more conv
5、enient 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
6、 growth of logn and,Compare the orders of growth of n! and 2n,Compare the orders of growth of 1/2n(n-1) and n2,2019/6/21,8,2012-2013-01Design and Analysis of Algorithm SCUN,Orders of growth of some important functions,All logarithmic functions loga n belong to the same class (log n) no matter what t
7、he logarithms base a 1 is All polynomials of the same degree k belong to the same class: aknk + ak-1nk-1 + + a0 (nk) Exponential functions an have different orders of growth for different as,2019/6/21,9,2012-2013-01Design and Analysis of Algorithm SCUN,Asymptotic Notation: o,o-notation Call f(n) = o
8、(g(n) if there exist positive constants c and n0 such that f(n) cg(n) for all n n0. Or, if , then f(n) = o(g(n) f(n) = 2n3+3n-5 = o(n4) f(n) = o(g(n) if and only if f(n) = O(g(n) , but g(n) O(f(n) nlogn = o(n2) means that nlogn = O(n2), but n2 O(nlogn),2019/6/21,10,2012-2013-01Design and Analysis of
9、 Algorithm SCUN,Asymptotic Notation,Using the o-notation, we can concisely express the following hierarchy of complexity classes. Polynomial complexity classes: 11) n! nn,2019/6/21,11,2012-2013-01Design and Analysis of Algorithm SCUN,Basic asymptotic efficiency classes,2019/6/21,12,2012-2013-01Desig
10、n and Analysis of Algorithm SCUN,Mathematical Background,Proof methods Floor and ceiling functions Summations Recurrence relations,2019/6/21,13,2012-2013-01Design and Analysis of Algorithm SCUN,Proof methods,Direct proof If n is an even integer, then n2 is an even integer. Indirect proof If n2 is an
11、 even integer, then n is an even integer. Proof by counterexample Let f(n)=n2+n+41 be a function defined on the set of nonnegative integers, proof f(n) is always a prime number. Proof by contradiction There are infinitely many primes.,2019/6/21,14,2012-2013-01Design and Analysis of Algorithm SCUN,Pr
12、oof methods (cont.),Mathematical induction Claim: S(n) is true for all 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)n1+nx for every real number x-1 and for every
13、natural number n.,2019/6/21,15,2012-2013-01Design and Analysis of Algorithm SCUN,Floor and ceiling functions,x: the floor of x, is the largest integer to x x: the 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
14、) = 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),2019/6/21,16,2012-2013-01Design and Analysis of Algorithm SCUN,Plan for Analysis of Nonrecursive Algorithms,Decide on a parameter indicating an inputs s
15、ize. 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.,2019/6/21,17,2012-2013-01Design and Analysis of Algorithm SCUN,Summations,A summation is a com
