为什么记忆比制表花费更多时间？

Question

我正在尝试解决这个基本的 Coin Change 动态规划问题：

给定一个值 N，如果我们想找 N 美分，并且我们有无限供应的每个 S = { S1, S2, .. , Sm} 值的硬币，我们有多少种方法可以找零改变？硬币的顺序无关紧要。这是我可以创建的解决方案：

我用三种通用方法解决了这个问题。 IE。递归、DP 记忆和 DP 制表。

#include <iostream>
#include <cstring>
#include <sys/time.h>
#include <limits.h>

using namespace std;

int max2(int a, int b)
{
    return (a>b) ? a : b;
}

int max3(int a, int b, int c)
{
    if(a>c)
        return (a>b) ? a : b;
    else
        return (c>b) ? c : b;
}

int min3(int a, int b, int c)
{
    if(a<c)
        return (a<b) ? a : b;
    else
        return (c<b) ? c : b;
}


int Coins_rec(int * S, int m, int n)
{
    if(n == 0)
        return 1;

    if(n < 0)
        return 0;

    if(m<=0 && n >=0){
        return 0;
    }

    return ( Coins_rec( S, m-1, n ) + Coins_rec( S, m, n - S[m-1] ) );
}


int memo[101][101] ;


int Coins_memoization(int * S, int m, int n)
{

    if(n == 0)
        return 1;

    if(n < 0)
        return 0;

    if(m<=0 && n >=0){
        return 0;
    }

    if(memo[m][n] !=-1) {

        return memo[m][n];
    } else
    {
        memo[m][n] = ( Coins_rec( S, m-1, n ) + Coins_rec( S, m, n - S[m-1] ) );
        return memo[m][n];
    }

}


int Coins_tabulation (int * S, int m, int n)
{
    int L[m+1][n+1] ;   //L[i][j] -> Minimum number of 'i' different types of coins required to make final amonut j
    int i, j;

    L[0][0] = 1;

    for(i=0;i<=m;i++){
        for(j=0;j<=n;j++){
            if (i == 0 && j >= 0) {
                L[0][j] = 0;
            } else if (i > 0 && j == 0) {
                L[i][0] = 1;
            } else {
                L[i][j] = ( (i >= 1) ? L[i-1][j] : 0 ) + ( (j - S[i-1] >=0) ? L[i][j - S[i-1]] : 0 ) ;
            }
        }
    }
    return L[m][n];
}       // -----  end of function Coins_tabulation  ----- 




int main() {

    int arr[] = {2, 5, 3, 6};
    int m = sizeof(arr)/sizeof(arr[0]);
    int n;

    cout << "Enter the amount" << endl;
    cin >> n;

    for(int i=0; i<=101; i++){
        for(int j=0; j<=101; j++){
            memo[i][j] = -1;
        }
    }

    struct timeval t0; gettimeofday(&t0 , NULL);

    cout << "Number of Ways = " << Coins_rec(arr, m, n) << endl;
    struct timeval t1; gettimeofday(&t1 , NULL);
    cout << "recursion : " << (t1.tv_sec - t0.tv_sec) << " seconds and " << (t1.tv_usec - t0.tv_usec) << " microseconds" << endl;

    cout << "Number of Ways (Memoization) = "  << Coins_memoization(arr, m, n) << endl;
    struct timeval t2; gettimeofday(&t2 , NULL);
    cout << "memoization : " << (t2.tv_sec - t1.tv_sec) << " seconds and " << (t2.tv_usec - t1.tv_usec) << " microseconds" << endl;


    cout << "Number of Ways (Tabulation) = "  << Coins_tabulation(arr, m, n) << endl;
    struct timeval t3; gettimeofday(&t3 , NULL);
    cout << "tabulation : " << (t3.tv_sec - t2.tv_sec) << " seconds and " << (t3.tv_usec - t2.tv_usec) << " microseconds" << endl;

    return 0;

}

。以下是结果：（通过标准输入获取的输入）

For n = 10
recursion : 0 seconds and 14 microseconds
memoization : 0 seconds and 17 microseconds
tabulation : 0 seconds and 17 microseconds

For n =100
recursion : 0 seconds and 1300 microseconds
memoization : 0 seconds and 1270 microseconds
tabulation : 0 seconds and 35 microseconds

我无法理解的是，为什么对于稍大的输入，记忆化花费的时间与简单的递归解决方案几乎相同？在这种情况下，记忆不应该比制表花费的时间更少吗，因为它跳过了矩阵中许多无用的计算，而这些计算必须在制表的情况下完成？

Answer 1

这是因为在记忆算法的递归步骤中，您实际上递归到 Coins_rec 而不是 Coins_memoization。一旦你解决了这个问题，你会发现对于更大的数字，记忆确实和制表一样快。例如，这是我机器上 100 的结果：

100
recursion : 0 seconds and 914 microseconds
memoization : 0 seconds and 18 microseconds
tabulation : 0 seconds and 16 microseconds

Answer 2

你应该期望记忆化会渐近地更快，但是对于以微秒为单位解决的微小输入，所有的赌注都不成立，实际上更快将高度依赖于硬件/系统。

为什么记忆比制表花费更多时间？

Why does memoizaion take more time than tabulation?

c++

recursion

memoization

dynamic-programming