再帰的および非再帰的アルゴリズムを使用して、フィボナッチ数列を見つけ、その時間計算量を分析します



Use Recursive Non Recursive Algorithms Find Fibonacci Sequence



1.再帰的ソリューション:

int fib(int n){ if(n == 1 || n ==0){ return 1 }else{ return fib(n-1)+fib(n-2) } }

時間計算量ソリューション:
画像
したがって、特性方程式を使用して時間計算量を解決できます



fib(n) = fib(n-1) + fib(n-2)The characteristic equation is:1 = x + x*x Solution is: p =1+5/2,q =1-5/2 After bringing in, we can see that its time complexity isO(n*n)

2.非再帰的ソリューション:

int fib2(int n){ int a,b,c a = 1 b = 1 c = 0 if(n == 0 || n == 1){ return 1 } for(int i =2i<=ni++){ c = a + b a = b b = c } return c }

今回の複雑さはO(n)であることは簡単にわかります。