面试中如何答好斐波那契数列fabnacci实现之java版？

2021-03-13 13:38

阅读：500

标签：ret turn 时间复杂次数描述最好 http fibonacci

背景

在计算科学中有一个著名的例子，斐波那契数列（fabnacci）序列，它是考察我们递归思想的运用。

技术图片

我们简单描述一下，F(n)满足下面的条件：

技术图片

当n=0时F(n)=0

当n=1时F(n)=1

当n>1时，F(n)=F(n-1)+F(n-2).

示例，F(n)的数组从0.....n

0，1，1，2，3，5，8，13，21，34，55，89，144，。。。。

那么如何实现呢？我们来看一下

java实现

1.两层递归

最简单的一种实现：

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

问题是：随着n的数值逐渐增多，时间和空间耗费太大，读者可以自行实验。在我的机器上n=50时就不能忍受了。

2.一层递归

考虑优化方式

 public static void main(String[] args) {
 long tmp=0;
 // TODO Auto-generated method stub
 int n=10;
 Long start=System.currentTimeMillis();
 for(int i=0;i

递归时间减少了到不到50%

3.不使用递归

最好的方式，不使用递归的方式来做。

 public static long fibonacci(int n){
 long before=0,behind=0;
 long result=0;
 for(int i=0;i

小结

面试官可以通过这个题目考察：1.是否熟悉基本的递归实现，递归思想在计算机科学属于最基本的思想。2：是否有优化的思路，通过时间和空间复杂度的转换来减少递归的次数。3：最终是否实现无递归来大大提升运算效率。