为什么记忆解决方案比普通递归解决方案慢？

Question

我正在实现一个计算第 n 个加泰罗尼亚语数字的函数。序列的公式如下：

我注意到记忆解决方案比普通递归解决方案慢。这是我的代码：

#include <bits/stdc++.h>
using namespace std;


int catalan_number_recursive(int n){
    if (n == 0) return 1;

    else{
        int ans = 0;
        for (int i = 0; i < n; i++){
            ans += catalan_number_recursive(i)*catalan_number_recursive(n - 1 - i);
        }

        return ans;
    }
}

int catalan_number_memo(int n, map<int, int> memo){
    memo[0] = memo[1] = 1;


    if (memo.count(n) != 0){
        return memo[n];
    }
    else{
        int ans = 0;
        for (int i = 0; i < n; i++){
            ans += catalan_number_memo(i, memo)*catalan_number_memo(n - 1 - i, memo);
        }

        memo[n] = ans;
        
        return memo[n];
    }
    

}

int main(){

    printf("Catalan Numbers - DP\n\n");

    int num = 12;

    auto start1 = chrono::high_resolution_clock::now();
    printf("%dth catalan number (recursive) is %d.\n", num, catalan_number_recursive(num));
    auto finish1 = chrono::high_resolution_clock::now();

    chrono::duration<double> elapsed1 = finish1 - start1;

    cout << "Time taken: " << elapsed1.count() << "s.\n\n";

    auto start2 = chrono::high_resolution_clock::now();
    printf("%dth catalan number (memo) is %d.\n", num, catalan_number_memo(num, {}));
    auto finish2 = chrono::high_resolution_clock::now();

    chrono::duration<double> elapsed2 = finish2 - start2;

    cout << "Time taken: " << elapsed2.count() << "s.\n";

    return 0;
}

n = 12 的代码输出为：

Catalan Numbers - DP

12th catalan number (recursive) is 208012.
Time taken: 0.006998s.

12th catalan number (memo) is 208012.
Time taken: 0.213007s.

此外，当我尝试使用 n = 20 时，它给了我一个负值，这是不正确的，但对于较小的值它是正确的。谢谢你的回答。

Answer 1

#include <bits/stdc++.h>
using namespace std;
int catalan_number_recursive(int n){
    if (n == 0) return 1;
    else{
        int ans = 0;
        for (int i = 0; i < n; i++){
            ans += catalan_number_recursive(i)*catalan_number_recursive(n - 1 - i);
        }

        return ans;
    }
}

int catalan_number_memo(int n, map<int, int>& memo){
    memo[0] = memo[1] = 1;


    if (memo.count(n) != 0){
        return memo[n];
    }
    else{
        int ans = 0;
        for (int i = 0; i < n; i++){
            ans += catalan_number_memo(i, memo)*catalan_number_memo(n - 1 - i, memo);
        }
        memo[n] = ans;
        return memo[n];
    }
}

int main(){

    printf("Catalan Numbers - DP\n\n");

    int num = 12;

    auto start1 = chrono::high_resolution_clock::now();
    printf("%dth catalan number (recursive) is %d.\n", num, catalan_number_recursive(num));
    auto finish1 = chrono::high_resolution_clock::now();

    chrono::duration<double> elapsed1 = finish1 - start1;

    cout << "Time taken: " << elapsed1.count() << "s.\n\n";

    auto start2 = chrono::high_resolution_clock::now();
    map<int, int> m;
    printf("%dth catalan number (memo) is %d.\n", num, catalan_number_memo(num, m));

    chrono::duration<double> elapsed2 = finish2 - start2;

    cout << "Time taken: " << elapsed2.count() << "s.\n";

    return 0;
}

这是您的代码，但只有一个更改 - 地图（现在是 map&）通过可变引用而不是值传递。

发生的事情是之前程序每次都在复制地图并将复制的地图作为递归参数传递，所以

0：你真的没有记住任何东西。在每个 return 点，学习值仅放入该函数独有的映射中，因此不会跨调用学习。它仍然是指数级的。

1：很慢。在每次递归时，你复制整个数据结构，而原始代码只有一个循环和。

现在我修复了它，程序运行如下：

Catalan Numbers - DP

12th catalan number (recursive) is 208012.
Time taken: 0.00236639s.

12th catalan number (memo) is 208012.
Time taken: 0.000103588s.

为什么记忆解决方案比普通递归解决方案慢？

Why is the memoized solution slower than the normal recursive solution?

c++

recursion

memoization

dynamic-programming