算法课件全121301ADA03算法分析基础－递归与非递归算法的分析方法.pptVIP

2007-2008-01《Design and Analysis of Algorithms》SCUEC 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 Goals of this lecture At the end of this lecture, you should Master asymptotic notations ? Be familial with the basic mathematical tools Master the analysis of non-recursive algorithms 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) for all n ? n0. f(n) = 2n3+3n-5 = ?(n3) f(n) = 2n4+1 = ?(n3) ??? Asymptotic Notation: ? 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: Orders of growth of some important functions All logarithmic functions loga n belong to the same class ?(log n) no matter what the logarithm’s 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 a’s Asymptotic Notation: o o-notation Call f(n) = o(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) Asymptotic Notation Using the o-notation, we can concisely express the following hierarchy of complexity classes. Polynomial complexity classes: 1 logn n nlogn n2 n3 Exponential complexity classes: an (a1) n! nn Basic asymptotic efficiency classes Mathematical Background Proof methods Floor and ceiling functions Summations Recurrence relations Proof methods Direct proof If n is an even integer, then n2 is an e