计算模型与算法技术：2-Fundamentals of the Analysis of Algorithm Efficiency

1、Chapter 2 Fundamentals of the Analysis of Algorithm EfficiencyCopyright 2007 Pearson Addison-Wesley. All rights reserved.222.1 Analysis Framework2.1 Analysis FrameworkIssues:correctnesstime efficiencyspace efficiencyoptimalityApproaches: theoretical analysisempirical analysisMeasuring an Inputs Size

2、(1) For example, polynomial inputPolynomials degree The number of its coefficients(2) For example, Matrix inputThere are two natural measures of size for this problem.Matrix order Total number of elements(3) For example, binary inputThe number b of bits in the ns binary representation4Units of Measu

3、ring Running TimeThe thing to do is to identify the most important operation of the algorithm, called the basic operation, the operation contributing the most to the total running time, and compute the number of times the basic operation is execute.5Theoretical analysis of time efficiencyTime effici

4、ency is analyzed by determining the number of repetitions of the basic operation as a function of input sizeBasic operation: the operation that contributes most towards the running time of the algorithm T(n) copC(n)running timeexecution timefor basic operationNumber of times basic operation is execu

5、tedinput size78Names for some orders of growth(1)Constant(logc n)Logarithmic (same order c)(logc n)Polylogarithmic(n)Linear(nc)Polynomial (for any c)(cn) Exponential (for c1)(n!)Factorial(With ca constant.)9Tractable vs. intractableA problem or algorithm with at most polynomial time complexity is co

6、nsidered tractable (or feasible). P is the set of all tractable problems.A problem or algorithm that has complexity greater than exponential is considered intractable (or infeasible).Note that n1,000,000 is technically tractable, but really very hard. nlog log log n is technically intractable, but e

7、asy. Such cases are rare though.10Computer Time ExamplesAssume time = 1 ns (109 second) per op, problem size = n bits, and #ops is a function of n, as shown.(125 kB)(1.25 bytes)Order of growth Most important: Order of growth within a constant multiple as nExample:How much faster will algorithm run o

8、n computer that is twice as fast?How much longer does it take to solve problem of double input size?Order of Growths Best-case, average-case, worst-caseFor some algorithms efficiency depends on form of input:Worst case: Cworst(n) maximum over inputs of size nBest case: Cbest(n) minimum over inputs o

9、f size nAverage case: Cavg(n) “average” over inputs of size nNumber of times the basic operation will be executed on typical inputNOT the average of worst and best caseExpected number of basic operations considered as a random variable under some assumption about the probability distribution of all

10、possible inputs14Best-case, average-case, worst-caseAlgorithmic complexity = cost of computation.Focus on time complexity for our course.Although space & energy are also important.Characterize complexity as a function of input size: worst-case, best-case, or average-case.Use orders-of-growth notatio

11、n to concisely summarize the growth properties of complexity functions.Example: Sequential searchWorst case : nBest case : 1 Average case: Recapitulation of the Analysis FrameworkBoth time and space efficiencies are measured as functions of the algorithms input size.Time efficiency is measured by co

12、unting the number of times the algorithms basic operation is executed. Space efficiency is measured by counting the number of extra memory units consumed by the algorithm.Recapitulation of the Analysis FrameworkThe efficiencies of some algorithms may differ significantly for inputs of the same size.

13、 For such algorithms, we need to distinguish between the worst-case, average-case and best-case efficiencies.The frameworks primary interest lies in the order of growth of the algorithms running time (extra memory units consumed) as its input size goes to infinity18182.2 Asymptotic Notations and Bas

14、ic Efficiency Classes2.2 Asymptotic Notations and Basic Efficiency ClassesA way of comparing functions that ignores constant factors and small input sizesO(g(n): class of functions f(n) that grow no faster than g(n)(g(n): class of functions f(n) that grow at same rate as g(n)(g(n): class of function

15、s f(n) that grow at least as fast as g(n)20Definition: O(g), at most order gLet g be any function RR.Define “at most order g”, written O(g), to be: f:RR | c,k: xk: f(x) cg(x).“Beyond some point k, function f is at most a constant c times g (i.e., proportional to g).”“f is at most order g”, or “f is

16、O(g)”, or “f=O(g)” all just mean that fO(g).Often the phrase “at most” is omitted.21Points about the definitionNote that f is O(g) so long as any values of c and k exist that satisfy the definition.But: The particular c, k, values that make the statement true are not unique: Any larger value of c an

17、d/or k will also work. You are not required to find the smallest c and k values that work. (Indeed, in some cases, there may be no smallest values!)However, you should prove that the values you choose do work.22“Big-O” Proof ExamplesShow that 30n+8 is O(n).Show c,k: nk: 30n+8 cn.Let c=31, k=8. Assum

18、e nk=8. Thencn = 31n = 30n + n 30n+8, so 30n+8 k: n2+1 cn2.Let c=2, k=1. Assume n1. Then cn2 = 2n2 = n2+n2 n2+1, or n2+10).It isnt evenless than 31neverywhere.But it is less than31n everywhere tothe right of n=8. nk=8 Big-O example, graphicallyIncreasing n Value of function n30n+8cn =31n30n+8O(n)24U

19、seful Facts about Big OBig O, as a relation, is transitive: fO(g) gO(h) fO(h)O with constant multiples, roots, and logs. f (in (1) & constants a,bR, with b0, af, f 1-b, and (logb f)a are all O(f).Sums of functions:If gO(f) and hO(f), then g+hO(f).25More Big-O factsc0, O(cf)=O(f+c)=O(fc)=O(f)f1O(g1)

20、f2O(g2) f1 f2 O(g1g2)f1+f2 O(g1+g2) = O(max(g1,g2) = O(g1) if g2O(g1) (Very useful!)26Orders of Growth - So FarFor any g:RR, “at most order g”,O(g) f:RR | c,k xk |f(x)| |cg(x)|.Often, one deals only with positive functions and can ignore absolute value symbols.“fO(g)” often written “f is O(g)” or “f

21、=O(g)”.The latter form is an instance of a more general convention.27Order-of-Growth Expressions“O(f)” when used as a term in an arithmetic expression means: “some function f such that fO(f)”.E.g.: “x2+O(x)” means “x2 plus some function that is O(x)”.Formally, you can think of any such expression as

22、 denoting a set of functions: x2+O(x) : g | fO(x): g(x)= x2+f(x)28Order of Growth EquationsSuppose E1 and E2 are order-of-growth expressions corresponding to the sets of functions S and T, respectively. Then the “equation” E1=E2 really means fS, gT : f=gor simply ST.Example: x2 + O(x) = O(x2) means

23、fO(x): gO(x2): x2+f(x)=g(x)29Useful Facts about Big O f,g & constants a,bR, with b0,af = O(f); (e.g. 3x2 = O(x2)f+O(f) = O(f); (e.g. x2+x = O(x2)Also, if f=(1) (at least order 1), then:|f|1-b = O(f); (e.g. x1 = O(x)(logb |f|)a = O(f). (e.g. log x = O(x)g=O(fg) (e.g. x = O(x log x)fg O(g) (e.g. x log

24、 x O(x)a=O(f) (e.g. 3 = O(x)30CaseLet are real number. is 31Definition: (g), exactly order gIf fO(g) and gO(f), then we say “g and f are of the same order” or “f is (exactly) order g” and write f(g).Another, equivalent definition:(g) f:RR | c1c2k0 xk: |c1g(x)|f(x)|c2g(x)| “Everywhere beyond some poi

25、nt k, f(x) lies in between two multiples of g(x).”32Rules for Mostly like rules for O( ), except: f,g0 & constants a,bR, with b0, af (f), but Same as with O. f (fg) unless g=(1) Unlike O.|f| 1-b (f), and Unlike with O. (logb |f|)c (f). Unlike with O.The functions in the latter two cases we say are s

26、trictly of lower order than (f).33 exampleDetermine whether:Quick solution:34Other Order-of-Growth Relations(g) = f | gO(f)“The functions that are at least order g.”o(g) = f | c0 k xk : |f(x)| 0 k xk : |cg(x)| 1. Then the following are true:1 log log n log n logk n logk n n1/k n n log n nk kn n! nn

27、38Review: Orders of GrowthDefinitions of order-of-growth sets, g:RRO(g) : f | c0 k xk |f(x)| 0 k xk |f(x)| |cg(x)|(g) : f | gO(f)(g) : f | go(f)(g) : O(g) (g)Big-ohBig-omegaBig-thetaEstablishing order of growth using the definitionDefinition: f(n) is in O(g(n) if order of growth of f(n) order of gro

28、wth of g(n) (within constant multiple),i.e., there exist positive constant c and non-negative integer n0 such that f(n) c g(n) for every n n0 Examples: 10n is O(n2)5n+20 is O(n)Some properties of asymptotic order of growthf(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

29、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) Establishing order of growth using limitslim T(n)/g(n) = 0 order of growth of 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) Example

30、s: 10n vs. n2 n(n+1)/2 vs. n2nLHpitals rule and Stirlings formulaLHpitals rule: If limn f(n) = limn g(n) = and the derivatives f, g exist, thenStirlings formula: n! (2n)1/2 (n/e)n f(n)g(n)limn= f (n)g (n)limnExample: log n vs. nExample: 2n vs. n!Orders of growth of some important functionsAll logari

31、thmic functions loga n belong to the same class (log n) no matter what the logarithms base a 1 isAll 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 asorder log n 0) order an order n! v then

32、 v := ai t3 return v t4 First, whats an expression for the exact total worst-case time? (Not its order of growth.)Times for each execution of each line.54Complexity analysis, cedure max(a1, a2, , an: integers) v := a1t1 for i := 2 to nt2 if ai v then v := ait3 return vt4w.c.t.c.: Times for e

33、ach execution of each line.55Complexity analysis, cont.Now, what is the simplest form of the exact () order of growth of t(n)?General PlanDecide on a parameter (or parameters) indicating an inputs size.Identify the algorithms basic operation. (As a rule, it is located in its innermost loop)Check whe

34、ther the number of times the basic operation is executed depends only on the size of an input. If it also depends on some additional property, the worst-case, average-case, and, if necessary, best-case efficiencies have to be investigated separately.56General Plan4. Set up a sum expressing the numbe

35、r of times the algorithms basic operation is executed.5. Using standard formulas and rules of sum manipulation, either find a closed-form formula for the count or, at the very least, establish its order of grown.57Example 2: Element uniqueness problem59Example 3: Matrix multiplicationExample 4: Gaus

36、sian eliminationAlgorithm GaussianElimination(A0.n-1,0.n)/Implements Gaussian elimination of an n-by-(n+1) matrix Afor i 0 to n - 2 do for j i + 1 to n - 1 do for k i to n do Aj,k Aj,k - Ai,k Aj,i / Ai,iFind the efficiency class and a constant factor improvement.Total number of multiplication62Examp

37、le 4: Counting binary digits It cannot be investigated the way the previous examples are. 64Example 5: Linear Searchprocedure linear search (x: integer, a1, a2, , an: distinct integers)i := 1t1while (i n x ai)t2 i := i + 1t3 if i n then location := it4 else location := 0t5 return locationt665Linear

38、search analysisWorst case time complexity order:Best case:Average case, if item is present:66Example 6: Binary Searchprocedure binary search (x:integer, a1, a2, , an: distinct integers, sorted smallest to largest) i := 1 j := nwhile iam then i := m+1 else j := mendif x = ai then location := i else l

39、ocation := 0return location(1)(1)(1)Key question:How many loop iterations?67Binary search analysisSuppose that n is a power of 2, i.e., k: n=2k.Original range from i=1 to j=n contains n items.Each iteration: Size ji+1 of range is cut in half.Loop terminates when size of range is 1=20 (i=j).Therefore

40、, the number of iterations is: k = log2n = (log2 n)= (log n)Even for n2k (not an integral power of 2),time complexity is still (log2 n) = (log n).Types of formulas for basic operations countExact formula e.g., C(n) = n(n-1)/2Formula indicating order of growth with specific multiplicative constant e.

41、g., C(n) 0.5 n2Formula indicating order of growth with unknown multiplicative constant e.g., C(n) cn2Useful summation formulas and rulesliu1 = 1+1+1 = u - l + 1Useful summation formulas and rulesIn particular, 1in1 = n - 1 + 1 = n (n) 1in i = 1+2+n = n(n+1)/2 n2/2 (n2) 1in i2 = 12+22+n2 = n(n+1)(2n+

42、1)/6 n3/3 (n3) 0in ai = 1 + a + an = (an+1 - 1)/(a - 1) for any a 1Useful summation formulas and rulesIn particular, 0in 2i = 20 + 21 + 2n = 2n+1 - 1 (2n ) (ai bi ) = ai bi cai = cai liuai = limai + m+1iuai 72722.4 Mathematical Analysis of Recursive AlgorithmsExample 1: Recursive evaluation of n!Def

43、inition: n ! = 1 2 (n-1) n for n 1 and 0! = 1Recursive definition of n!: F(n) = F(n-1) n for n 1 and F(0) = 1 Size: Basic operation:Recurrence relation:Solving the recurrence for M(n)M(n) = M(n - 1) + 1, M(0) = 0M(n) = M(n - 1) + 1 = M(n - 2) + 1 + 1= M(n - 2) + 2 = M(n - 3) + 1 + 1= M(n - 3) + 2M(n

44、) = M(n - 1) + 1 = = M(n - i) + i = M(n - n) + n = n Plan for Analysis of Recursive AlgorithmsDecide 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

45、, the worst, average, and best cases must be investigated separately.)Set up a recurrence relation with an appropriate initial condition expressing the number of times the basic op. is executed.Solve the recurrence (or, at the very least, establish its solutions order of growth) by backward substitu

46、tions or another method.Example 2: The Tower of Hanoi PuzzleRecurrence for number of moves: 123Solving recurrence for number of movesM(n) = M(n-1) + 1 + M(n-1) for n 1M(n) = 2M(n-1) + 1 for n 1, M(1) = 1M(n) = 2M(n-1) + 1 = 22M(n-2) + 1+1=2*2*M(n-2)+2+1 = 2*2 2M(n-3) + 1+2+1 = 2*2*2*M(n-3)+2*2+2+1 =

47、 =2(n-1)*M(n-(n-1)+2(n-1)-1 =2(n-1)*M(1)+2(n-1)-1 =2(n-1)+2(n-1)-1=2n-1Tree of calls for the Tower of Hanoi PuzzleExample 3: Counting #bits8081812.5 Fibonacci numbersFibonacci 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) = 1G

48、eneral 2nd order linear homogeneous recurrence with constant coefficients: aX(n) + bX(n-1) + cX(n-2) = 0Empirical analysis of time efficiencySelect a specific (typical) sample of inputsUse physical unit of time (e.g., milliseconds) or Count actual number of basic operations executionsAnalyze the emp

49、irical dataSolving 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 + r nParticular

50、 solution can be found by using initial conditionsApplication 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) =0, F(1)=1:868788Algorithm for Comput

51、ing Fibonacci Number9091Computing Fibonacci numbersDefinition-based recursive algorithmNonrecursive definition-based algorithmExplicit formula algorithmLogarithmic algorithm based on formula:F(n-1) F(n)F(n) F(n+1) 0 11 1=nfor n1, assuming an efficient way of computing matrix powers.9495952.6 Empiric

52、al Analysis of Algorithm2.6 Empirical Analysis of Algorithm Some seeming simple algorithms have been proved be very difficult to analyze with mathematical precision and certainty. This is especially true for average-case analysis. The principal alternative to the mathematical analysis of an algorith

53、ms efficiency is its empirical analysis. This approach implies the steps spelled out in the following plan.General Plan for Empirical Analysis of Algorithm Time EfficiencyUnderstand the experiments purpose.Decide on the efficiency metric M to be measured and the measurement unit (an operations count

54、 vs. a time unit).Decide on characteristics of the input sample (its range, size, and so on)Prepare a program implementing the algorithm(s) for the experimentation.Generate a sample of inputs.Run the algorithm(s) on the samples inputs and record the data observed.Analyze the data obtained.97The firs

55、t alternative is to insert a counter into a program implementing the algorithm to count the number of times the algorithms basic operation is executed.The second alternative is to time the program implementing the algorithm in question.Clock (C+) currentTimeMills() (JAVA)98However,1. a systems time

56、is typically not very accurate.2. given the high speed of modern computers, the running time may fail to register at all and be reported as zero.3. on a computer running under a time-sharing system, the reported time may include the time spent by the CPU on other programs.99Measuring time spent on d

57、ifferent segments of a program can point a bottleneck in the programs performance that can be missed by an abstract deliberation about the algorithms basic operation.Getting such data called profiling is an important resource in the empirical analysis of an algorithms running time; the data in quest

58、ion can usually be obtained from the system tools available in most computing environments.100Whether you decide to measure the efficiency by basic operation counting or by time clocking, you will need to decide on a sample of inputs for the experiment.The principal advantage of size changing according to a pattern is that its impact is easier to analyze.Another important issue concerning sizes in an experiments samp