动态规划(非递归)、递归、备忘录法的性能比较及分析_备忘录方法和递归方法差一为啥

通过斐波那契数列的求解对动态规划、递归、备忘录法分别实现的算法性能进行比较。

public class Fibonacci {
    public static void main(String[] args) {
        int i = 30;
        long l1 = System.nanoTime();
        System.out.println(diGui(i));
        long l2 = System.nanoTime();
        System.out.println("递归实现耗费时间"+(l2-l1)+"纳秒");

        System.out.println(beiWangLu(i));
        long l3 = System.nanoTime();
        System.out.println("递归添加备忘录实现耗费时间"+(l3-l2)+"纳秒");

        System.out.println(dg(i));
        long l4 = System.nanoTime();
        System.out.println("非递归实现耗费时间"+(l4-l3)+"纳秒");
    }

    /**
     * 递归实现斐波那契数列
     * @param n 输入参数
     */
    public static int diGui(int n){
        if(n == 1 || n == 2){
            return 1;
        }
        return diGui(n-1)+diGui(n-2);
    }

    /**
     * 备忘录法实现斐波那契
     * @param n 输入参数
     * @return
     */
    private static HashMap<Integer,Integer> map = new HashMap<>();
    public static int beiWangLu(int n){
        if(n == 1 || n == 2){
            return 1;
        }
        if(map.get(n) != null){
            return map.get(n);
        }
        int result = beiWangLu(n-1) + beiWangLu(n-2);
        map.put(n,result);
        return result;
    }

    /**
     * 动态规划实现菲波那切(非递归)
     * @param n 输入参数
     * @return
     */
    public static int dg(int n){
        if(n == 1 || n == 2){
            return 1;
        }
        int a = 1;
        int b = 1;
        int temp = 0;
        for(int i = 2; i < n; i++){
            temp = a+b;
            a = b;
            b = temp;
        }
        return temp;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

输出结果：

832040
递归实现耗费时间5736100纳秒
832040
递归添加备忘录实现耗费时间212700纳秒
832040
非递归实现耗费时间82800纳秒
1
2
3
4
5
6

        因为递归对一些已经计算过的值进行了重复计算，例如求n=6时的值，如果使用递归算法会计算f(5)和f(4)的值，当求f(5)的值的时候又会对f(4)的值进行求解，进行了重复计算，时间复杂度是O(2^n)，如下面的图所示，可以看到递归进行设计的时候算法的效率还是挺慢的，虽然便于我们理解，但是在实际开发过程中要减少对递归的使用。

        对递归进行改进，使用备忘录法计算的时候，是对之前计算过的值进行了保存，从而避免了多次求同一值的时间浪费，从而大大提高了效率，可以看到通过缓存中间的数据，做了大量地剪枝的工作，同样的f(4),f(3),f(2)，都只算一遍了,省去了大量的重复计算，问题的规模从二叉树变成了单链表（即 n），时间复杂度变成了 O(n)，不过由于哈希表缓存了所有的子问题的结果，空间复杂度是 O(n)。

        采用自底向上的规律去求解，f(n) 就是定义的每个子问题的状态（DP 状态），f(n) = f(n-1) + f(n-2) 就是状态转移方程，即 f(n) 由 f(n-1), f(n-2) 这两个状态转移而来,由于每个子问题只与它前面的两个状态，所以我们只要定义三个变量，自底向上不断循环迭代即可。