循环方式求解斐波那契数列

一时失言乱红尘 2023-01-14 05:55 133阅读 0赞

斐波那契数列（Fibonacci sequence）是1、1、2、3、5、8、13、21、34、55...

对于斐波那契数列的第n项求解，通常是使用递归方式实现，如下

public static int fbNum(int n) {
    		if (n==1 || n==2) return 1;
    		else return fbNum(n-1) + fbNum(n-2);
    	}

使用递归方式计算斐波那契数时，第n项总是须要先计算出第n-1项和第n-2项，运行时间*T(N)![\\geqslant][geqslant]T(N-1)+T(N-2)*。由于T(N)作为斐波那契数满足同样的递推关系并具有相同的初始条件，因此，T(N)事实上是以斐波那契数相同的速度增长而指数级增长。

另一方面，由于计算F![\_\{n\}][n]所须要的只是F![\_\{n-1\}][n-1]和F![\_\{n-2\}][n-2]，因此，只须要记录最近算出的两个斐波那契数即可，可以推到出*O(N)*算法

public static int fibonacci(int n) {
    		if (n == 1 || n == 2) return 1;
    		
    		int last = 1;
    		int nextToLast = 1;
    		int answer = 2;
    		for (int i=3; i<=n; i++) {
    			answer = last + nextToLast;
    			nextToLast = last;
    			last = answer;
    		}
    		return answer;
    	}

通过测试，看一下两个方法的时间消耗情况

public static void main(String[] args) throws NumberFormatException, IOException {
    		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    		String input;
    		while ((input = br.readLine()) != null) {
    			int num = Integer.parseInt(input);
    			long start = System.currentTimeMillis();
    			int num1 = fbNum(num);
    			long end = System.currentTimeMillis();
    			System.out.println("fbNum():n=" + num +" num1 = " + num1 + " cost " + (end-start));
    			
    			start = System.currentTimeMillis();
    			num1 = fibonacci(num);
    			end = System.currentTimeMillis();
    			System.out.println("dp():n=" + num + " num1 = " + num1 + " cost " + (end-start));
    		}
    	}

执行测试结果如下

10
    fbNum():n=10 num1 = 55 cost 0
    fibonacci():n=10 num1 = 55 cost 0
    20
    fbNum():n=20 num1 = 6765 cost 1
    fibonacci():n=20 num1 = 6765 cost 0
    25
    fbNum():n=25 num1 = 75025 cost 1
    fibonacci():n=25 num1 = 75025 cost 0
    30
    fbNum():n=30 num1 = 832040 cost 3
    fibonacci():n=30 num1 = 832040 cost 0
    35
    fbNum():n=35 num1 = 9227465 cost 32
    fibonacci():n=35 num1 = 9227465 cost 0
    40
    fbNum():n=40 num1 = 102334155 cost 337
    fibonacci():n=40 num1 = 102334155 cost 0
    45
    fbNum():n=45 num1 = 1134903170 cost 3837
    fibonacci():n=45 num1 = 1134903170 cost 0

在取前10个数字时，两个算法的效率基本差别不大，都可以瞬间完成

在计算第20个数字时，递归要耗时1毫秒，而循环瞬间完成

在计算第30个数字时，递归要耗时3毫秒，而循环瞬间完成

在计算第35个数字时，递归要耗时32毫秒，而循环瞬间完成

在计算第40个数字时，递归要耗时337毫秒，而循环瞬间完成

在计算第45个数字时，递归要耗时3837毫秒，而循环瞬间完成

从以上测试可以看出，斐波那契数越大时，循环的优势越明显。

[geqslant]: https://latex.codecogs.com/gif.latex?%5Cgeqslant
[n]: https://latex.codecogs.com/gif.latex?_%7Bn%7D
[n-1]: https://latex.codecogs.com/gif.latex?_%7Bn-1%7D
[n-2]: https://latex.codecogs.com/gif.latex?_%7Bn-2%7D