java程序员到底该不该了解一点算法,一个简单的递归计算斐波那契数列的案例说明算法对程序的重要性

为什么说 “算法是程序的灵魂这句话一点也不为过”,递归计算斐波那契数列的第50项是多少?

方案一:只是单纯的使用递归,递归的那个方法被执行了250多亿次,耗时1分钟还要多。

方案二:用一个map去存储之前计算出的某一项的数据map<n, feibo(n)>,当后面项需要使用前面项的值时,只需要从map中取即可,递归的那个方法仅仅行了97次,耗时还不到1ms。

而这仅仅是计算第50项的值,再往大去计算的话,方案一耗时会更久,因为执行的次数是呈现指数增加的,而且递归的次数过多还有可能会出现栈溢出的问题。

演示如下所示:

 1 package recursion;
 2 
 3 import java.util.HashMap;
 4 import java.util.Map;
 5 
 6 import org.junit.Test;
 7 
 8 /**      
 9  * @author: 攻城狮小白
10  * @creationTime: 2017年11月27日 上午9:47:51
11  * @description: 斐波那契数列结合备忘录算法的简单使用
12  */
13 public class MemorandumDemo {
14     //计算方法执行次数
15     private long count;
16     //map集合作为一个备忘录,用来保存已经计算出来的fibo(n)的值
17     private Map<Integer, Long> map = new HashMap<>();
18     
19     //方式一:不使用map集合作为备忘录缓存数据
20     public long fibo(Integer n) {
21         count++;
22         if(n == 1 || n == 2){
23             return 1;
24         }else{    
25             return fibo(n-1) + fibo(n-2);
26         }
27     }
28     //方式二:使用map集合作为备忘录缓存数据
29     public long fibo2(Integer n) {
30         count++;
31         if(n == 1 || n == 2){
32             return 1;
33         }else{    
34             if(!map.containsKey(n)){
35                 map.put(n, fibo2(n-1) + fibo2(n-2));
36             }
37             return map.get(n);
38         }
39     }
40     
41     @Test
42     public void test1(){
43         long start = System.currentTimeMillis();
44         long result = fibo(50);
45         long end = System.currentTimeMillis();;
46         System.out.println("计算结果:" + result);
47         System.out.println("耗费时间:" + (end-start) + "毫秒");
48         System.out.println("方法执行次数:"+count);
49         /*测试结果
50          * 计算结果:12586269025
51          * 耗费时间:77318毫秒
52          * 方法执行次数:25172538049
53         */
54     }
55     
56     @Test
57     public void test2(){
58         long start = System.currentTimeMillis();
59         long result = fibo2(50);
60         long end = System.currentTimeMillis();;
61         System.out.println("计算结果:" + result);
62         System.out.println("耗费时间:" + (end-start) + "毫秒");
63         System.out.println("方法执行次数:" + count);
64         /*测试结果
65          * 计算结果:12586269025
66          * 耗费时间:0毫秒
67          * 方法执行次数:97
68         */
69     }
70 }