package suanfa1;
import java.util.*;
public class Main {
public static int fib1(int n){
if( n <= 1) return n;
return fib1( n - 1) + fib1 ( n - 2);
}
public static int fib2(int n ){
if(n <= 1) return n;
int first = 0;
int second = 1;
for(int i = 0; i < n - 1;i++){
int sum = first + second;
first = second;
second = sum;
}
return second;
}
public static void main(String args[]){
System.out.print(fib2(20));
}
}
分析以上两种不同的算法实现的斐波那契数列第n项的运算。
可以发现第一个函数和第二个函数的效率具有很大的差别。
对fib1来说： 他进行了大量的重复操作。如图。 O（2的n次方）。
对fib2来说，它的时间复杂度为O(n);
可见，不同的算法对时间的影响如此之高，故在工作时找到一个高效的算法十分重要。
标签：int,不同,fib1,second,算法,static,public,运行 From： https://www.cnblogs.com/yyhjj1314/p/17038511.html