题目:求斐波那契数列的第 项。斐波那契数列的定义如下:
斐波那契数列的定义对于大家来说应该很熟了,即斐波那契数列的第 项等于前两项之和。
public static int fibonacci(int n) {
if (n <= 0) {
return 0;
} else if (n == 1 || n == 2) {
return 1;
}
return fibonacci(n -1) + fibonacci(n - 2);
}
但是上面的程序有个很大的问题,就是运行的速度很慢,我们先看一下运行的时间,再来分析为何这么慢
public static void main(String[] args) {
long start = System.nanoTime();
System.out.println(fibonacci(45));
long end = System.nanoTime();
System.out.println((end - start) / 1000000 + " ms");
}
结果如下
1134903170
4272 ms
在我的电脑上,计算斐波那契数列第 所需的时间为4272 ms
,这时因为有重复的计算,我们在计算 #card=math&code=f%2845%29&height=20&width=39) 时,需要计算 #card=math&code=f%2844%29&height=20&width=39) 和 #card=math&code=f%2843%29&height=20&width=39),而在计算 #card=math&code=f%2844%29&height=20&width=39) 还需要计算 #card=math&code=f%2843%29&height=20&width=39),这样计算就重复了,它的时间复杂度为#card=math&code=O%282%5En%29&height=20&width=43)。
现在我们考虑另一种解法,我们分析上面的计算是因为重复的计算,如果我们利用前面已有的结果,那么所需的时间即可大大减少,程序如下
public static int fibonacci(int n) {
if (n <= 0) {
return 0;
} if (n == 1 || n == 2) {
return 1;
}
int firstNumber = 1;
int secondNumber = 1;
int result = 0;
for (int i = 2; i < n; i++) {
result = firstNumber + secondNumber;
firstNumber = secondNumber;
secondNumber = result;
}
return result;
}
上面的时间复杂度只有#card=math&code=O%28n%29&height=20&width=36),我们再次计算第 项
1134903170
0 ms
所需的时间连 1 ms
都不需要,速度相比上面提高的不是一星半点。
题目:青蛙跳台阶。一只青蛙一次可以跳上 级台阶,也可以跳上 级台阶。求该青蛙跳上一个 级的台阶总共有多少种跳法。
其实这个问题仔细想想就可以发现,这道问题就是斐波那契数列的一个变体。考虑第 级台阶,青蛙最后一步到达第 级台阶只有两种方法,从 级跳 级,或者从 级跳 级,设青蛙跳上一个 级台阶有 种跳法,那么可以得到这样的关系式
%20%3D%20f(n%20-%201)%20%2Bf(n%20-%202)%0A#card=math&code=f%28n%29%20%3D%20f%28n%20-%201%29%20%2Bf%28n%20-%202%29%0A&height=20&width=198)
这个式子不就是斐波那契数列的通项嘛,所以程序的写法也是一样的,不过它们的初始条件不一样,简单分析就可以得到
%20%3D%201%20%5C%5C%5C%5C%0Af(2)%20%3D%202%0A#card=math&code=f%281%29%20%3D%201%20%5C%5C%5C%5C%0Af%282%29%20%3D%202%0A&height=45&width=724)
具体的程序参考上面。