国外算法设计与分析课件03

1、Fundamentals of the Analysis of Algorithm Efficiency Algorithm analysis framework Asymptotic notations Analysis of non-recursive algorithms Analysis of recursive algorithms Copyright Li Zimao 2007-2008-1 SCUECExpected OutcomesThe students should be able toList the key steps in an algorithms analysis

2、 frameworkDefine the three asymptotic notations and explain their relationsCompare the asymptotic growth rate of two given functions by using the definition of asymptotic notation or LimitsDescribe the key steps in analysis of a non-recursive algorithm and a recursive algorithmUse different ways to

3、transform a recurrence relation into its closed formAnalyze the time complexity of recursive algorithm for computing the nth Fibonacci numberCopyright Li Zimao 2007-2008-1 SCUECAnalysis of AlgorithmsAnalysis of algorithms means to investigate an algorithms efficiency with respect to resources: runni

4、ng time and memory space. Time efficiency: how fast an algorithm runs. Space efficiency: the space an algorithm requires.Typically, algorithms run longer as the size of its input increasesWe are interested in how efficiency scales wrt input sizeCopyright Li Zimao 2007-2008-1 SCUECAnalysis FrameworkM

5、easuring an inputs sizeMeasuring running time Orders of growth (of the algorithms efficiency function)Worst-base, best-case and average-case efficiencyCopyright Li Zimao 2007-2008-1 SCUECMeasuring Input SizesEfficiency is defined as a function of input size.Input size depends on the problem.Example

6、1, what is the input size of the problem of sorting n numbers?Example 2, what is the input size of adding two n by n matrices?Copyright Li Zimao 2007-2008-1 SCUECUnits for Measuring Running TimeShould we measure the running time using standard unit of time measurements, such as seconds, minutes?Depe

7、nds on the speed of the computer.Count the number of times each of an algorithms operations is executed.Difficult and unnecessaryCount the number of times an algorithms basic operation is executed.Basic operation: the operation that contributes the most to the total running time. For example, the ba

8、sic operation is usually the most time-consuming operation in the algorithms innermost loop.Copyright Li Zimao 2007-2008-1 SCUECOrder of growth Most important: Order of growth within a constant multiple as nExample:How much faster will algorithm run on computer that is twice as fast?How much longer

9、does it take to solve problem of double input size?Copyright Li Zimao 2007-2008-1 SCUECInput size and basic operation examplesProblemInput size measureBasic operationSearching for key in a list of n itemsNumber of lists items, i.e. nKey comparisonMultiplication of two matricesMatrix dimensions or to

10、tal number of elementsMultiplication of two numbersChecking primality of a given integer nnsize = number of digits (in binary representation)DivisionTypical graph problem#vertices and/or edgesVisiting a vertex or traversing an edgeCopyright Li Zimao 2007-2008-1 SCUECTheoretical Analysis of Time Effi

11、ciencyTime efficiency is analyzed by determining the number of repetitions of the basic operation as a function of input size. running timeexecution timefor the basic operationNumber of times the basic operation is executedinput sizeT(n) copC (n)The efficiency analysis framework ignores the multipli

12、cative constants of C(n) and focuses on the orders of growth of the C(n).Assuming C(n) = (1/2)n(n-1), how much longer will the algorithm run if we double the input size?Copyright Li Zimao 2007-2008-1 SCUECOrders of GrowthOrders of growth: consider only the leading term of a formula ignore the consta

13、nt coefficient.Exponential-growth functionsCopyright Li Zimao 2007-2008-1 SCUECCopyright Li Zimao 2007-2008-1 SCUECWorst-Case, Best-Case, and Average-Case EfficiencyAlgorithm efficiency depends on the input size nFor some algorithms efficiency depends on type of input.Example: Sequential SearchProbl

14、em: Given a list of n elements and a search key K, find an element equal to K, if any.Algorithm: Scan the list and compare its successive elements with K until either a matching element is found (successful search) or the list is exhausted (unsuccessful search)Given a sequential search problem of an

15、 input size of n, what kind of input would make the running time the longest? How many key comparisons?Copyright Li Zimao 2007-2008-1 SCUECSequential Search AlgorithmALGORITHM SequentialSearch(A0.n-1, K)/Searches for a given value in a given array by sequential search/Input: An array A0.n-1 and a se

16、arch key K/Output: Returns the index of the first element of A that matches K or 1 if there are no matching elementsi 0while i n and Ai K doi i + 1if i =Copyright Li Zimao 2007-2008-1 SCUECSome Properties of Asymptotic Order of Growth f(n) O(f(n) f(n) O(g(n) iff g(n) (f(n) If f (n) O(g (n) and g(n)

17、O(h(n) , then f(n) O(h(n) Note similarity with a bIf f1(n) O(g1(n) and f2(n) O(g2(n) , then f1(n) + f2(n) O(maxg1(n), g2(n) The analogous assertions are true for the -notation and -notation.Copyright Li Zimao 2007-2008-1 SCUECSome Properties of Asymptotic Order of GrowthIf f1(n) O(g1(n) and f2(n) O(

18、g2(n) , then f1(n) + f2(n) O(maxg1(n), g2(n)Implication: The algorithms overall efficiency will be determined by the part with a larger order of growth.For example, 5n2 + 3nlogn O(n2)Copyright Li Zimao 2007-2008-1 SCUECUsing Limits for Comparing Orders of Growthlimn T(n)/g(n) = 0 order of growth of

19、T(n) 0 order of growth of T(n) = order of growth of g(n) order of growth of T(n) order of growth of g(n) Examples: 10n vs. 2n2 n(n+1)/2 vs. n2 logb n vs. logc nCopyright Li Zimao 2007-2008-1 SCUECLHpitals ruleIf limn f(n) = limn g(n) = and the derivatives f , g exist, Then f(n)g(n)limn= f (n)g (n)li

20、mn Example: log2n vs. n 2n vs. n!Stirlings formula: n! (2n)1/2 (n/e)nCopyright Li Zimao 2007-2008-1 SCUECOrders of growth of some important functionsAll logarithmic functions loga 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

21、 to the same class: aknk + ak-1nk-1 + + a0 (nk). Exponential functions an have different orders of growth for different as.order log n 0) order an order n! 0F(n) = 1if n = 0F(n) = n * F(n-1)if n 0if n=0 return 1/base caseelse return F (n -1) * n/general caseCopyright Li Zimao 2007-2008-1 SCUECExampl

22、e 1: Recursive evaluation of n ! Two Recurrences The one for the factorial function value: F(n)The one for number of multiplications to compute n!, M(n)F(n) = F(n 1) * n for every n 0F(0) = 1M(n) = M(n 1) + 1 for every n 0M(0) = 0M(n) (n)Copyright Li Zimao 2007-2008-1 SCUECSteps in Mathematical Anal

23、ysis of Recursive AlgorithmsDecide on parameter n indicating input sizeIdentify algorithms basic operationCheck whether the number of times the basic operation is executed may vary on different inputs of the same size. (If it may, the worst, average, and best cases must be investigated separately.)S

24、et up a recurrence relation and initial condition(s) for C(n)-the number of times the basic operation will be executed for an input of size n (alternatively count recursive calls). Solve the recurrence or estimate the order of magnitude of the solution by backward substitutions or another method (se

25、e Appendix B)Copyright Li Zimao 2007-2008-1 SCUECExample 2: The Tower of Hanoi PuzzleCopyright Li Zimao 2007-2008-1 SCUECThe Towers of Hanoi PuzzleRecurrence RelationsDenote the total number of moving as M(n)Succinctness vs. efficiencyM(n) = 2M(n 1) + 1 for every n 0M(1) = 1Be careful with recursive

26、 algorithms because their succinctness mask their inefficiency.M(n) (2n)Copyright Li Zimao 2007-2008-1 SCUECExample 3: Find the number of binary digits in the binary representation of a positive decimal integerCompute number of additions: A(n) = A(n/2)+1 with A(1) = 0Copyright Li Zimao 2007-2008-1 S

27、CUECSmoothness RuleLet f(n) be a nonnegative function defined on the set of natural numbers. f(n) is called smooth if it is eventually nondecreasing andf(2n) (f(n)Functions that do not grow too fast, including logn, n, nlogn, and n where =0 are smooth.Smoothness rule (Appendix B)let T(n) be an event

28、ually nondecreasing function and f(n) be a smooth function. If T(n) (f(n) for values of n that are powers of b, where b=2, then T(n) (f(n) for any n.A(n) = A(n/2)+1 with A(1) = 0 A(n) (log n) Copyright Li Zimao 2007-2008-1 SCUECIn fact, we can prove A(n) = log n is the solution to above recurrence.C

29、opyright Li Zimao 2007-2008-1 SCUECFibonacci numbersThe Fibonacci numbers:0, 1, 1, 2, 3, 5, 8, 13, 21, The Fibonacci recurrence:F(n) = F(n-1) + F(n-2) F(0) = 0 F(1) = 1General 2nd order linear homogeneous recurrence with constant coefficients: aX(n) + bX(n-1) + cX(n-2) = 0Copyright Li Zimao 2007-200

30、8-1 SCUECSolving aX(n) + bX(n-1) + cX(n-2) = 0Set up the characteristic equation (quadratic) ar2 + br + c = 0Solve to obtain roots r1 and r2General solution to the recurrenceif r1 and r2 are two distinct real roots: X(n) = r1n + r2nif r1 = r2 = r are two equal real roots: X(n) = rn + nr nParticular

31、solution can be found by using initial conditionsCopyright Li Zimao 2007-2008-1 SCUECApplication to the Fibonacci numbersF(n) = F(n-1) + F(n-2) or F(n) - F(n-1) - F(n-2) = 0Characteristic equation: Roots of the characteristic equation:General solution to the recurrence:Particular solution for F(0) =

32、0, F(1)=1:Copyright Li Zimao 2007-2008-1 SCUECGolden RatioCopyright Li Zimao 2007-2008-1 SCUECEfficiency for Recursive Computation of Fibonacci NumberNumber of additions:A(n) = A(n-1) + A(n-2) + 1 for n 1A(0) = 0, A(1) = 0 A(n) = F(n+1) 1 (n)Copyright Li Zimao 2007-2008-1 SCUECComputing Fibonacci nu

33、mbersDefinition-based recursive algorithm (n)Nonrecursive definition-based algorithm (n)Explicit formula algorithmLogarithmic algorithm based on formula: (log n)F(n-1) F(n)F(n) F(n+1)0 11 1=nfor n1, assuming an efficient way of computing matrix powers.Copyright Li Zimao 2007-2008-1 SCUECImportant Recurrence TypesDecrease-by-one recurrencesA decrease-by-one algorithm solves a problem by exploiting a relationship between a given instance of size n and a smaller size n 1. Example: n!The recurrence equation for investigating the ti