如何计算动态规划(记忆)算法中的大0

Question

如何计算DP算法的大0 。我开始意识到我计算算法的方法并不总是有效。我会用一些简单的技巧来提取大0是什么。例如，如果我正在计算以下算法的无记忆版本(删除缓存机制)，我将查看递归方法调用自己的次数(在本例中为3次)。然后我把这个值提高到n，得到0 (3^n)DP就完全不对了因为递归堆栈没有那么深。我的直觉告诉我DP解的大0等于O(n^3)我们如何口头解释我们是如何想出这个答案的 ?更重要的是，什么技术可以用来找到类似问题的大0 。既然是DP，我确定子问题的数量很重要我们如何计算子问题的数量

public class StairCase {
    public int getPossibleStepCombination(int n) {
        Integer[] memo = new Integer[n+1];
        return getNumOfStepCombos(n, memo);
    }
    private int getNumOfStepCombos(int n, Integer[] memo) {
        if(n < 0) return 0;
        if(n == 0) return 1;
        if(memo[n] != null) return memo[n];
        memo[n] = getNumOfStepCombos(n - 1, memo) + getNumOfStepCombos(n - 2, memo) + getNumOfStepCombos(n-3,memo);
        return memo[n];
    }
}

Answer 1

第一行3只比较int值，通过索引访问数组，并查看Integer引用是否为null。这些都是O(1)，所以唯一的问题是这个方法被递归调用了多少次。

这个问题很复杂，所以我经常作弊。我只是用计数器看看发生了什么。(为此，我将您的方法设置为静态，但通常您应该尽可能避免静态可变状态)。

static int counter = 0;
public static int getPossibleStepCombination(int n) {
    Integer[] memo = new Integer[n+1];
    return getNumOfStepCombos(n, memo);
}
private static int getNumOfStepCombos(int n, Integer[] memo) {
    counter++;
    if(n < 0) return 0;
    if(n == 0) return 1;
    if(memo[n] != null) return memo[n];
    memo[n] = getNumOfStepCombos(n - 1, memo) + getNumOfStepCombos(n - 2, memo) + getNumOfStepCombos(n-3,memo);
    return memo[n];
}
public static void main(String[] args) {
    for (int i = 0; i < 10; i++) {
        counter = 0;
        getPossibleStepCombination(i);
        System.out.print(i + " => " + counter + ", ");
    }
}

这个程序打印

0 => 1, 1 => 4, 2 => 7, 3 => 10, 4 => 13, 5 => 16, 6 => 19, 7 => 22, 8 => 25, 9 => 28, 

所以看起来最终的计数器值是由3n + 1给出的。

在一个更复杂的例子中，我可能无法发现模式，所以我将前几个数字(e.g. 1, 4, 7, 10, 13, 16)输入到在线整数序列百科全书中，然后我通常会被带到一个包含模式简单公式的页面。

一旦你用这种方法找出了这个规则，你就可以开始理解这个规则为什么有效了。

这就是我如何理解3n + 1的来源。对于n的每个值，您只需要执行

行

memo[n] = getNumOfStepCombos(n - 1, memo) + getNumOfStepCombos(n - 2, memo) + getNumOfStepCombos(n-3,memo);

正好一次

。这是因为我们正在记录结果，并且仅在答案尚未计算时才执行这一行。

因此，当我们从n == 5开始时，我们运行一行正好5次;一次是n == 5，一次是n == 4，一次是n == 3，一次是n == 2，一次是n == 1。这是3 * 5 == 15乘以getNumOfStepCombos从自身调用的方法。该方法也从自身外部被调用一次(从getPossibleStepCombination)，所以总调用次数为3n + 1。

因此这是一个O(n)算法。

如果算法中有非O(1)的行，则不能直接使用该计数器方法，但通常可以采用该方法。

Answer 2

Paul的回答在技术上没有错，但有点误导。我们应该通过函数对输入大小变化的响应来计算大0符号。Paul的答案O(n)使复杂度看起来是线性时间，而实际上它是表示数字n所需比特数的指数。例如，n=10有~30个计算，m=2个比特。N =100有300次计算，m=3位。N =1000有~3000个计算，m=4位。

我相信你的函数的复杂性将是O(2^m)，其中m是表示n所需的位数。我参考了https://www.quora.com/Why-is-the-Knapsack-problem-NP-complete-even-when-it-has-complexity-O-nW很多我的答案。