《15-16-01ADA04(算法分析基础-递归与非递归算法的分析方法II)》由会员分享，可在线阅读，更多相关《15-16-01ADA04(算法分析基础-递归与非递归算法的分析方法II)（21页珍藏版）》请在金锄头文库上搜索。
1、Review of last class,Asymptotic notations Mathematical Background Analysis of non-recursive algorithms,2018/10/20,2,2015-2016-01 Design and Analysis of Algorithm SCUN,Fundamentals of the Analysis of Algorithm Efficiency (III),Chapter 2,1、 Analysis of recursive algorithms 2、 Fibonacci numbers,2018/10
2、/20,4,2015-2016-01 Design and Analysis of Algorithm SCUN,Goals of this lecture,At the end of this lecture, you should Master the plan for analysis of recursive algorithm Master the methods for solving recurrence relations Be familiar with Fibonacci number,2018/10/20,5,2015-2016-01 Design and Analysi
3、s of Algorithm SCUN,Plan for Analysis of Recursive Algorithms,Decide 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, the worst, average, and best
4、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 substitutions or another method.,2018
5、/10/20,6,2015-2016-01 Design and Analysis of Algorithm SCUN,Recurrence Relations,A recurrence relation can be put into an equivalent closed form without the recursion Generation function Characteristics equation Substitution,A recurrence relation is a recursive form of an equation, for example:,2018
6、/10/20,7,2015-2016-01 Design and Analysis of Algorithm SCUN,Example 4: Recursive evaluation of n!,Definition: n ! = 1 2 (n-1) n for n 1 and 0! = 1,Input size:,Basic operation:,Best, worst, average case:,Recurrence relation:,n,Multiplication,no,T(n) = T(n-1) + 1,Recursive definition of n!: F(n) = F(n
7、-1) n for n 1 and F(0) = 1, T(0) = 0,2018/10/20,8,2015-2016-01 Design and Analysis of Algorithm SCUN,Solving the recurrence for T(n),T(n) = T(n-1) + 1, T(0) = 0 Begin by looking at a series of equations with decreasing values of n:,2018/10/20,9,2015-2016-01 Design and Analysis of Algorithm SCUN,Then
8、, we substitute back into the first equation:,Solving the recurrence for T(n) (cont.),2018/10/20,10,2015-2016-01 Design and Analysis of Algorithm SCUN,We stop when we get to T(0):,Solving the recurrence for T(n) (cont.),How many “+1” terms are there? Notice we increase them with each substitution.,2
9、018/10/20,11,2015-2016-01 Design and Analysis of Algorithm SCUN,We must have n of the “+ 1” terms because we,Solving the recurrence for T(n) (cont.),So, our closed form of the equation is:,2018/10/20,12,2015-2016-01 Design and Analysis of Algorithm SCUN,Example 5: The Tower of Hanoi Puzzle,Recurrenc
10、e for number of moves:,2018/10/20,13,2015-2016-01 Design and Analysis of Algorithm SCUN,Solving recurrence for number of moves,M(n) = 2M(n-1) + 1, M(1) = 1,2018/10/20,14,2015-2016-01 Design and Analysis of Algorithm SCUN,Example 6: Counting #bits,Input size:,Basic operation:,Best, worst, average cas
11、e:,Recurrence relation:,n,Addition,no,A(n) = A(n/2) +1 A(1) = 0,Closed form:,2018/10/20,15,2015-2016-01 Design and Analysis of Algorithm SCUN,Example 7 Fibonacci numbers,The 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) = 1,General ho
12、mogeneous 2nd order linear recurrence with constant coefficients:aX(n) + bX(n-1) + cX(n-2) = 0,2018/10/20,16,2015-2016-01 Design and Analysis of Algorithm SCUN,Solving aX(n) + bX(n-1) + cX(n-2) = 0,Set up the characteristic equation (quadratic)ar2 + br + c = 0,Solve to obtain roots r1 and r2,General
13、 solution to the recurrence if r1 and r2 are two distinct real roots: X(n) = r1n + r2n if r1 = r2 = r are two equal real roots: X(n) = rn + nr n,Particular solution can be found by using initial conditions,2018/10/20,17,2015-2016-01 Design and Analysis of Algorithm SCUN,Application to the Fibonacci
14、numbers,Characteristic equation:,r2 - r - 1=0,F(n) = F(n-1) + F(n-2) or F(n) - F(n-1) - F(n-2) = 0,Roots of the characteristic equation:,General solution to the recurrence:,Particular solution for F(0) =0, F(1)=1:,2018/10/20,18,2015-2016-01 Design and Analysis of Algorithm SCUN,Computing Fibonacci n
15、umbers,Definition-based recursive algorithm,ALGORITHM F(n)/Input: A nonnegative integer n/Output: The nth Fibonacci numberif n 1 return nelse return F(n-1) + F(n-2),Input size:,Basic operation:,Best, worst, average case:,Recurrence relation:,n,Addition,no,A(n) = A(n-1) + A(n-2) +1 A(0) = 0, A(1) =0,
16、Closed form:,2018/10/20,19,2015-2016-01 Design and Analysis of Algorithm SCUN,Computing Fibonacci numbers,Explicit formula algorithm,ALGORITHM Fib(n)/Input: A nonnegative integer n/Output: The nth Fibonacci numberF0 0; F1 0for i 2 to n doFi Fi-1 + Fi-2 return F(n),Nonrecursive definition-based algorithm,
