Fibonacci

入门链接

定义：F(0) = 0, F(1) = 1, F(n) = F(n - 1) + F(n - 2)(n >= 2，n ∈ N*)
最简单！证明黄金（斐波那契）数列通项公式

图解

详解

时间复杂度讲解(斐波那契)
三种时间复杂度算法求解斐波那契数列
斐波那契时间复杂度和空间复杂度分析

标准写法

public static long fibonacci(long number) {
    if ((number == 0) || (number == 1))
        return number;
    else
        return fibonacci(number - 1) + fibonacci(number - 2);
}

要点

• 递归版的斐波那契时间复杂度是O(2^n)，空间复杂度（树的高度）是O(n)