3

这是我正在做的关于动态编程的一个小练习。我有以下功能：

在此处输入图像描述

我必须用两种方法（自上而下的记忆和自下而上）来编程这个函数。

这是我目前为自下而上所做的：

    public static int functionBottomUp (int n){
            int [] array = new int[n+1];
            array[0] = 1;
            for(int i = 1; i < array.length; i++){
                if(i == 1)
                    array[i] = array[i - 1];
                else {
                    for(int p = 0; p < i; p ++)
                        array[i] += array[p];
                }
            }
            return array[n];
   }

对于记忆：

public static int functionMemoization(int n){
        int[] array = new int[n+1];     
        for(int i = 0; i < n; i++)
            array[i] = 0;
        return compute(array, n);
    }

    private static int compute(int[] array, int n){
        int ans = 0;
        if(array[n] > 0)
            return array[n];
        if(n == 0 || n == 1)
            ans = 1;
        else 
            for(int i = 0; i < n; i++)
                ans += compute(array, i);
        array[n] = ans;
        return array[n];
    }

我得到了正确的输出，但现在我正在努力计算两者的复杂性。

首先，复杂性是f(n)因为2^n拨打f(3)电话7和f(0)拨打f(4)电话15（f(0)我知道这不是正式的证明，但这只是为了给我一个想法）。

但现在我被困在计算这两个函数的复杂性上。

自下而上：

我会说复杂性是 O(n) （因为for(int i = 1; i < array.length; i++)）但是有这个内部循环for(int p = 0; p < i; p ++)，我不知道这是否会改变复杂性。

记忆化：

显然这是一个最复杂的 O(n)，因为第一个循环初始化了数组。但我不知道计算函数如何修改这种复杂性。

有人可以为我澄清一下吗？

4

1 回答 1

2

让我们来看看你的功能。这是自下而上的 DP 版本：

public static int functionBottomUp (int n){
        int [] array = new int[n+1];
        array[0] = 1;
        for(int i = 1; i < array.length; i++){
            if(i == 1)
                array[i] = array[i - 1];
            else {
                for(int p = 0; p < i; p ++)
                    array[i] += array[p];
            }
        }
        return array[n];
}

为了计算正在完成的工作，我们可以查看完成某个任意 i 的循环迭代 i 需要多少工作。请注意，如果 i = 1，则完成的工作是 O(1)。否则，循环运行时由这部分占用：

for(int p = 0; p < i; p ++)
    array[i] += array[p];

这个循环的时间复杂度与 i 成正比。这意味着循环迭代我（或多或少）工作。因此，完成的总工作是（大约）

1 + 2 + 3 + ... + n = Θ(n 2 )

因此，这里的运行时间是 Θ(n 2 ) 而不是 O(n) ，正如您在问题中所推测的那样。

现在，让我们看一下自上而下的版本：

public static int functionMemoization(int n){
    int[] array = new int[n+1];     
    for(int i = 0; i < n; i++)
        array[i] = 0;
    return compute(array, n);
}

private static int compute(int[] array, int n){
    int ans = 0;
    if(array[n] > 0)
        return array[n];
    if(n == 0 || n == 1)
        ans = 1;
    else 
        for(int i = 0; i < n; i++)
            ans += compute(array, i);
    array[n] = ans;
    return array[n];
}

您最初执行 Θ(n) 工作以将数组归零，然后调用compute以计算所有值。您最终将使用值填充所有array值，并且每个数组元素将只执行一次，因此确定时间复杂度的一种方法是确定每个数组条目需要多少工作来填充它。在这种情况下，完成的工作由这部分决定：

for(int i = 0; i < n; i++)
    ans += compute(array, i);

由于您正在记忆值，因此在确定对值 n 评估函数所需的工作时，我们可以假设每个递归调用都花费时间 O(1)；当我们总结所有 n 时，将考虑实际工作。和以前一样，这里所做的工作与 n 成正比。因此，由于 n 的范围从 1 到 n，因此所做的工作大致为

1 + 2 + 3 + ... + n = Θ(n 2 )

这又比您估计的 O(n) 更多的工作。

但是，有一种更快的方法来评估这种复发。查看 f(n) 的前几个值：

  • f(0) = 1
  • f(1) = 1
  • f(2) = 2
  • f(3) = 4
  • f(4) = 8
  • f(5) = 16
  • ...
  • f(n) = 2 n-1

因此，我们得到

  • f(0) = 1
  • f(n) = 2 n-1如果 n > 0

因此，以下函数评估f时间：

int f(int n) {
    return n == 0? 1 : 1 << (n - 1);
}

假设您正在使用固定大小的整数（例如，32 位或 64 位整数），这需要时间 O(1)。如果您使用的是任意精度整数，这将花费时间 Θ(n)，因为如果不写出 Θ(n) 位，就无法表达 2 n-1 ，但是如果我们在此假设下运行，则原始代码也需要进行调整，以考虑添加的成本。为简单起见，我将忽略它或将其作为练习留给读者。^_^

希望这可以帮助！

于 2013-10-21T19:20:29.263 回答