Fibonacci数列的1点思考哈哈

Fibonacci数列的一点思考哈哈
Fibonacci数列对于我们计算机的学生来说，太熟悉不过，但是今天在看书的时候还是发现了点新的东西。

一般的找出Fibonacci数的方法如下：

public static long fib(long index){if (index == 0) {return 0;}else if(index == 1){return 1;}else{return fib(index - 1)+fib(index -2);}}

其复杂度显然为：O(2的n次方)，递归问题，与汉诺塔问题的复杂度一致。

下面给出一种较好的方法，其算法复杂度为O(n)：

package MyAlgorithom;import java.util.Scanner;public class ImprovedFibonacci {public static void main(String[] args) {/*创建一个用户输入*/Scanner scanner = new Scanner(System.in);System.out.println("输入一个Fibonacci数列的index：");int index = scanner.nextInt();System.out.println("Fibonacci number at index"+index+" is "+fib(index));}public static long fib(long n){long f0 = 0;long f1 = 1;long f2 = 1;if (n == 0) {return f0;} else if(n == 1){return f1;} else if(n == 2){return f2;}for (int i = 3; i <= n; i++) {f0 = f1;f1 = f2;f2 = f1+f0;}return f2;}}

程序结果：
输入一个Fibonacci数列的index：
100
Fibonacci number at index100 is 3736710778780434371

“灵活”计算机程序的精髓，这种“移位”思想比递归好多了吧哈哈。

查看更多 下一篇