题目如下：
求第n个斐波那契数
斐波那契数列：这个数列从第3项开始，每一项都等于前两项之和。
下标 0 1 2 3 4 5 6 7
数列 0 1 1 2 3 5 8 13
方法一：
public class Test {
public static long fun1(long n){
if(n<=1) return n;
return fun1(n-1)+fun1(n-2);
}
采用递归的方式：
存在问题
n越大运行的就越慢
时间复杂度：O(2^n)
看fun1方法被调用了多少次，调用了多少次就是执行了多少次
如果传入的是5调用fun1（4）和fun1（3）依次推导共调用O(2^n)
方法二：
public static int fun2(int n){
if(n<=1) return n;
int first=0;
int second=1;
//下标为n的数字需要循环加n-1次
for (int i = 0; i
//每次加都是前两个
int sum=first+second;
//相加之前second需要当作下一次相加的first
first=second;
//相加的结果要给下一个second
second=sum;
}
return second;
}
时间复杂度：O(n)
相对方法一来说，这个方法运行更快
