题目如下：

  求第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 <n-1 ; i++) {     //每次加都是前两个     int sum=first+second;     //相加之前second需要当作下一次相加的first     first=second;     //相加的结果要给下一个second     second=sum; } return second;    }

时间复杂度：O(n)相对方法一来说，这个方法运行更快