一、最优算法 迭代
一个迭代，时间复杂度O(N)
/**
* 迭代法
* 通过不断的交换f1 f2 fn的值 注意控制好边界
*
* @param n
* @return
*/
public static int fib(int n) {
int f0 = 0, f1 = 1;
if (n <= 0) return 0;
if (n == 1) return 1;
int fn = 0;
for (int i = 2; i <= n; i++) {
fn = f0 + f1;
f0 = f1;
f1 = fn;
}
return fn;
}
迭代的方式还有一种，就是用数组存起来，然后取array[n]
/**
* 借助数组，
*
* @param n
* @return
*/
public static int fib(int n) {
int array[] = new int[n + 1];
array[0] = 0;
array[1] = 1;
for (int i = 2; i <= n; i++) {
array[i] = array[i - 1] + array[i - 2];
}
return array[n];
}
二、最简单算法 递归
/**
* 递归是有明显缺陷的
* 当数组过大的时候会出现StackOverFlow
*
* @param n
* @return
*/
public static int fib(int n) {
if (n <= 0) return 0;
if (n == 1) return 1;
return fib(n - 1) + fib(n - 2);
}
