Fibonacci - HolmesJJ/Data-Structures-and-Algorithms GitHub Wiki
入门链接
**定义: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)