Recursive time complexity analysis — Fibonacci sequence

The article directories

• • Fibonacci sequence
  • Second, recursive solution of Fibonacci sequence
  • Time complexity analysis

Fibonacci sequence

• Fibonacci sequence refers to a sequence in which the value of the current term equals the sum of the first two terms:

• The recursion formula of this sequence is as follows:

F (n) (n = 0) = {1, 1 (n = 1) f (n – 1) + f (n – 2) (n > 2) (n) = f \ begin {cases} 1 & (n = 0) \ \ 1 & (n = 1) \ \ f (n – 1) + f (n – 2) & (n > 2) f (n) = {cases} \ end ⎩ ⎪ ⎨ ⎪ ⎧ 11 f (n – 1) + f (n – 2) (n = 0) (n = 1) (n > 2)

Second, recursive solution of Fibonacci sequence

int f(unsigned int n) {
	if(n <= 1) {
		return 1;
	}
	return f(n- 1) + f(n2 -);
}
Copy the code

Time complexity analysis

• The process of graphical solution is as follows:

• This is a binary tree, the height of the tree is N, so the number of nodes visited in depth-first search is 2n 2^n 2n. However, if you look closely, the height of the leftmost node must be larger than the height of the right node, so it is not a strict complete binary tree. To explore its actual time complexity, let’s change the code:

int f(unsigned int n) {
	++c[n];
	if(n <= 1) {
		return 1;
	}
	return f(n- 1) + f(n2 -);
}
Copy the code

• I added a line of code++c[n];Let’s see how many times f(n) f(n) f(n) will be called under different n, n, n cases;
• The table measured is as follows:

• Observe the growth trend of C [n] C [n] C [n], first exclude the arithmetic sequence, and then see if it conforms to the arithmetic sequence. Let’s try to calculate the value of C [n]/ C [n−1] C [n]/c[n]. The table is as follows:

• It is observed that as n n n increases, c[n]/c[n−1] c[n]/c[n-1] C [n]/c[n−1] gets closer and closer to a constant, which is: 2 5 −1 ≈1.618034 \frac {2}{\ SQRT 5-1} \approx 1.618034 5 −12≈1.618034
• When n approaches infinity, the following formula is satisfied: c[n]= 2 5 −1 c[n−1] C [n]= \frac {2}{\ SQRT 5-1} c[n-1] c[n]=5 −12c[n−1]
• After solving the geometric sequence, we can get: C [n] = 2 5 − 1 c[n − 1] = (2 5 − 1) 2 C [n − 2] =.. = (2 5 − 1) n c[n] = \frac {2}{\ SQRT 5-1} c[n-1] = (\frac {2}{ \sqrt 5 – 1})^2 c[n-2] = … = (\ frac {2} {} \ SQRT 5-1) ^ n c [n] = 5-12 [n – 1) = c (5-12) [n – 2) = 2 c… N = (5-12)
• So, the time complexity of the recursive solution of the Fibonacci sequence is: O((2 5 −1)n) O((\frac {2}{\ SQRT 5-1})^n) O((5 −12)n)