recursion - 递归记忆化比递归慢

Question

我试图了解时间复杂度方面，使用递归运行斐波那契与使用内存和递归运行递归会发生什么。

我预计仅使用递归 - (2^n) - 会比使用记忆化和递归 - O(n) 慢。也就是说，内存是进行动态编程的一种方法，一种优化技术......所以，我希望它更快。

首先，使用递归运行。

时间:10ms leetcode:击败 23%

public int fib(int n) {
    if (n < 2) {
        return n;
    }
    return fib(n-1) + fib(n-2)
}

其次，使用记忆化和递归来运行。

时间:29ms leetcode:击败 13%

public int fib(int n) {
    if (n < 2) {
        return n;
    } 
    int[] dp = new int[n+1];
    if (dp[n] != 0){
        return dp[n];  
    } 
    int result = fib(n-1) + fib(n-2);
    dp[n] = result;
    return result;
}

您可以看到单独使用递归速度更快。为什么？

Answer 1

你没有在内存。该数组不会从一个调用到下一个调用共享，每个调用都会创建自己的数组。它很慢，因为您做了额外的工作，为每个调用分配一个数组，但从未获得任何好处，并且该函数仍然像以前一样是树递归的。

如果您想内存，您需要共享存储内存数据的数据结构，以便新的调用可以访问先前调用的结果。

有不同的方法可以做到这一点，一种非常基本的方法是将内存数据作为另一个参数提供:

// initial call used by outside world, sets up the array
public int fib(int n) {
    int[] dp = new int[n + 1];
    return fib(n, dp);
}

// overloaded version that takes memo data, used internally
public int fib(int n, int[] dp) {

    if (n < 2) {
        return n;
    } 
    if (dp[n] != 0){
        return dp[n];  
    } 
    int result = fib(n-1, dp) + fib(n-2, dp);
    System.out.printf("call %d = %d\n", n, result);
    dp[n] = result;
    return result;
}

添加一个 printf 来表明每个值只计算一次，打印出来

call 2 = 1
call 3 = 2
call 4 = 3
call 5 = 5
call 6 = 8
call 7 = 13
call 8 = 21
call 9 = 34
call 10 = 55