## Fibonacci算法的三种实现与性能比较 原

longrmlife

``````import java.util.ArrayList;
import java.util.List;

public class Fibonacci {

/**
* 递归算法：不断调用自身实现深度计算
* @param n
* @return
*/
public static Long recursiveCompute(int n) {
if (n <= 2)
return 1L;
else
return recursiveCompute(n - 1) + recursiveCompute(n - 2);
}

/**
* 非递归cache算法：用一个List缓存所有从1~n的Fibonacci值
* @param n
* @return
*/
public static Long cacheCompute(int n) {
if (n <= 2)
return 1L;

List<Long> results = new ArrayList<Long>();

int length = -1;
while ((length = results.size()) < n)
results.add(results.get(length - 2) + results.get(length - 1));
return results.get(n - 1);
}

/**
* 非递归swap算法：只用两个变量l1、l2来保存Fibonacci值，不断update和swap
* @param n
* @return
*/
public static Long swapCompute(int n) {
if (n <= 2)
return 1L;

long l1 = 1;
long l2 = 1;

int index = 2;
while (index < n - 1) {
long l = l2;
l2 = l1 + l2;
l1 = l;
index++;
}
return l1 + l2;
}

public static void testTime(int n) {
Long result = 0L;

long start = System.nanoTime();
result = recursiveCompute(n);
long end = System.nanoTime();
System.out.println("Recursive Compute: " + result + "\tUse Time: " + (end - start));

start = System.nanoTime();
result = cacheCompute(n);
end = System.nanoTime();
System.out.println("Cache Compute: " + result + "\tUse Time: " + (end - start));

start = System.nanoTime();
result = swapCompute(n);
end = System.nanoTime();
System.out.println("Swap Compute: " + result + "\tUse Time: " + (end - start));
}

public static void main(String[] args) {
System.out.println("Compute Fibonacci(10):");
testTime(10);
System.out.println("\nCompute Fibonacci(20):");
testTime(20);
System.out.println("\nCompute Fibonacci(30):");
testTime(30);
System.out.println("\nCompute Fibonacci(40):");
testTime(40);
System.out.println("\nCompute Fibonacci(50):");
testTime(50);
}

}``````

``````Compute Fibonacci(10):
Recursive Compute: 55	Use Time: 26944
Cache Compute: 55	Use Time: 52444
Swap Compute: 55	Use Time: 4330

Compute Fibonacci(20):
Recursive Compute: 6765	Use Time: 1528093
Cache Compute: 6765	Use Time: 26463
Swap Compute: 6765	Use Time: 1443

Compute Fibonacci(30):
Recursive Compute: 832040	Use Time: 17896390
Cache Compute: 832040	Use Time: 48595
Swap Compute: 832040	Use Time: 1924

Compute Fibonacci(40):
Recursive Compute: 102334155	Use Time: 2385636507
Cache Compute: 102334155	Use Time: 54850
Swap Compute: 102334155	Use Time: 1924

Compute Fibonacci(50):
Recursive Compute: 12586269025	Use Time: 287928822445
Cache Compute: 12586269025	Use Time: 76501
Swap Compute: 12586269025	Use Time: 2887``````

``````Compute Fibonacci(100):
Cache Compute: 3736710778780434371	Use Time: 274730
Swap Compute: 3736710778780434371	Use Time: 10104

Compute Fibonacci(1000):
Cache Compute: 817770325994397771	Use Time: 1330826
Swap Compute: 817770325994397771	Use Time: 44746

Compute Fibonacci(10000):
Cache Compute: -2872092127636481573	Use Time: 4596307
Swap Compute: -2872092127636481573	Use Time: 326211

Compute Fibonacci(50000):
Cache Compute: -806788626697678875	Use Time: 14161801
Swap Compute: -806788626697678875	Use Time: 1218240``````
1. Recursive算法由于不断调用自身，深度计算过多，性能非常低下，当n>=50时，Recursive算法所花的时间已经很难容忍了；
2. Cache算法和Swap算法只是在while循环里不断计算和更新，其中Cache算法每次将计算值保存在List中，占用的内存过多，性能也没有Swap的好；

### longrmlife

"二分查找(Binary Search)"与"斐波那契查找(Fibonacci Search)"

2015/09/30
916
0

fnqtyr45
2017/11/22
0
0
LeetCode算法题-Fibonacci Number（Java实现）

02/15
0
0
HTML5 Web Worker的使用

Web Workers 是 HTML5 提供的一个javascript多线程解决方案，我们可以将一些大计算量的代码交由web Worker运行而不冻结用户界面。 一：如何使用Worker Web Worker的基本原理就是在当前javas...

WolfX
2016/02/24
16
0
java递归算法实现

Fibonacci数列：1，1，2，3，5，8，13…… public classFab { public static void main(String args[]){ } private static int fab(int index){ } } 程序分析： 这个实例是非常经典的实例，主......

2016/03/01
46
0

Taro 兼容 h5 踩坑指南

dkvirus
52分钟前
3
0
Spring boot 静态资源访问

0. 两个配置 spring.mvc.static-path-patternspring.resources.static-locations 1. application中需要先行的两个配置项 1.1 spring.mvc.static-path-pattern 这个配置项是告诉springboo......

moon888

3
0
hash slot（虚拟桶）

4
0
Kafka 原理和实战

vivo互联网技术

19
0
java数据类型

audience_1

9
0