我是一个斐波那契程序员，因为我每天都在改昨天和前天的bug～
数列：0 1 1 2 3 5 8 13 21...
斐波那契数列由 就是从0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
有俩种算法，直接上递归，一种根据规律作出优化：
public class Main { public static void main(String[] args) { System.out.println(fib(7)); System.out.println(fib1(8)); } //递归 private static int fib(int n){ if (n <= 1) return n; return fib(n - 1) + fib(n - 2); } //优化后 private static int fib1(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; } }
比较俩种算法，我们用大O表示数据规模n的复杂度
忽略常数 系数 低阶
第一种递归算法：
分析得出：fib(n - 1) + fib(n - 2) 执行多少次就是算法的复杂度，fib(n - 1) + fib(n - 2)执行多少次就是 fib(int n)被调用多少次。算法时间复杂度为O(2^n)
第二种算法在于：
保存每一次的计算结果，不用每一次去重复计算，时间复杂度是O(n)
原文：https://www.cnblogs.com/zhvip/p/14003026.html