1、Fundamentals of the Analysis of Algorithm Efficiency(III)Chapter 21、Analysis of non-recursive algorithms(II)2、Analysis of recursive algorithms 2022-12-2032010-2011-01 Design and Analysis of Algorithm SCUECExample 2:Element uniqueness problemInput size:Basic operation:Best,worst,average case:Summatio
2、n:Cworst=nComparisonyes2120(1)1()2nnij in nn2022-12-2042010-2011-01 Design and Analysis of Algorithm SCUECExample 3:Matrix multiplicationInput size:Basic operation:Best,worst,average case:Summation:nMultiplicationno111330001()nnnijknn2022-12-2052010-2011-01 Design and Analysis of Algorithm SCUECExam
3、ple 4:Counting binary digits Input size:Basic operation:Best,worst,average case:Summation:nComparisonnoAbout logn2022-12-2062010-2011-01 Design and Analysis of Algorithm SCUECPlan for Analysis of Recursive AlgorithmsbDecide on a parameter indicating an inputs size.bIdentify the algorithms basic oper
4、ation.bCheck 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.)bSet up a recurrence relation with an appropriate initial condition expressing the number of times the basic op
5、.is executed.bSolve the recurrence(or,at the very least,establish its solutions order of growth)by backward substitutions or another method.2022-12-2072010-2011-01 Design and Analysis of Algorithm SCUECRecurrence RelationsbA recurrence relation is a recursive form of an equation,for example:bA recur
6、rence relation can be put into an equivalent closed form without the recursion Generation function Characteristics equation Substitution(1)0()(1)1TT nT n2022-12-2082010-2011-01 Design and Analysis of Algorithm SCUECExample 5:Recursive evaluation of n!Definition:n!=1 2 (n-1)n for n 1 and 0!=1Recursiv
7、e definition of n!:F(n)=F(n-1)n for n 1 and F(0)=1Input size:Basic operation:Best,worst,average case:Recurrence relation:nMultiplication noT(n)=T(n-1)+1,T(0)=02022-12-2092010-2011-01 Design and Analysis of Algorithm SCUECSolving the recurrence for T(n)T(n)=T(n-1)+1,T(0)=0bBegin by looking at a serie
8、s of equations with decreasing values of n:T()T(1)1T(1)T(2)1T(2)T(3)1T(3)T(4)1T(4)T(5)1nnnnnnnnnn2022-12-20 102010-2011-01 Design and Analysis of Algorithm SCUECbThen,we substitute back into the first equation:T()T(1)1T()(T(2)1)1T()(T(3)1)1)1T()(T(4)1)1)1)1T()(T(5)1)1)1)1)1nnnnnnnnnnSolving the recu
9、rrence for T(n)(cont.)2022-12-20 112010-2011-01 Design and Analysis of Algorithm SCUECbWe stop when we get to T(0):bHow many“+1”terms are there?Notice we increase them with each substitution.T()T(1)1T()(T(2)1)1T()(T(0)1)1)1)1nnnnnSolving the recurrence for T(n)(cont.)2022-12-20 122010-2011-01 Design
10、 and Analysis of Algorithm SCUECbWe must have n of the“+1”terms because we did n substitutions:bSo,our closed form of the equation is:11T()T(0)1ninT()nnSolving the recurrence for T(n)(cont.)2022-12-20 132010-2011-01 Design and Analysis of Algorithm SCUECExample 6:The Tower of Hanoi Puzzle123Recurren
11、ce for number of moves:2022-12-20 142010-2011-01 Design and Analysis of Algorithm SCUECSolving recurrence for number of movesM(n)=2M(n-1)+1,M(1)=12022-12-20 152010-2011-01 Design and Analysis of Algorithm SCUECExample 7:Counting#bitsInput size:Basic operation:Best,worst,average case:Recurrence relat
12、ion:nAddition noA(n)=A(n/2)+1 A(1)=0Closed form:2()logA nn 2022-12-20 162010-2011-01 Design and Analysis of Algorithm SCUECExample 8 Fibonacci 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 homogeneous linear recurrence with
13、 constant coefficients:aX(n)+bX(n-1)+cX(n-2)=02022-12-20 172010-2011-01 Design and Analysis of Algorithm SCUECSolving aX(n)+bX(n-1)+cX(n-2)=0bSet up the characteristic equation(quadratic)ar2+br+c=0bSolve to obtain roots r1 and r2bGeneral solution to the recurrenceif r1 and r2 are two distinct real r
14、oots:X(n)=r1n+r2nif r1=r2=r are two equal real roots:X(n)=rn+nr nbParticular solution can be found by using initial conditions2022-12-20 182010-2011-01 Design and Analysis of Algorithm 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
15、the characteristic equation:General solution to the recurrence:Particular solution for F(0)=0,F(1)=1:r2 -r-1=01,211 4(1)1522r1515()22nnF n115115()2255nnF n2022-12-20 192010-2011-01 Design and Analysis of Algorithm SCUECComputing Fibonacci numbers1.Definition-based recursive algorithmALGORITHM F(n)/I
16、nput:A nonnegative integer n /Output:The nth Fibonacci number if n 1 return n else return F(n-1)+F(n-2)Input size:Basic operation:Best,worst,average case:Recurrence relation:nAddition noA(n)=A(n-1)+A(n-2)+1 A(0)=0,A(1)=0Closed form:11115115()12255nnA n2022-12-20 202010-2011-01 Design and Analysis of
17、 Algorithm SCUECComputing Fibonacci numbers3.Explicit formula algorithmALGORITHM Fib(n)/Input:A nonnegative integer n /Output:The nth Fibonacci number F0 0;F1 0 for i 2 to n do Fi Fi-1+Fi-2 return F(n)2.Nonrecursive definition-based algorithmInput size:Basic operation:Best,worst,average case:Summation:nAddition211()ninn 115115()2255nnF nNoThe End2022-12-20 222010-2011-01 Design and Analysis of Algorithm SCUECAssignment bPreview:chapter 3bExercises:No 1,3,4 of exercises 2.4 No 6 of exercises 2.5
