如何计算动态规划（Memoization）算法的Big O

Question

我将如何计算 DP 算法的大 O。我开始意识到我计算算法的方法并不总是有效。我会使用简单的技巧来提取 Big O 是什么。例如，如果我正在评估下面算法的 none 记忆版本（删除缓存机制），我会查看递归方法在这种情况下调用自身的次数 3 次。然后我会将该值提高到 n，给出 O(3^n)。使用 DP 根本不正确，因为递归堆栈没有那么深。我的直觉告诉我，DP 解决方案的大 O 将是 O(n^3)。 我们如何口头解释我们是如何得出这个答案的。 更重要的是什么技术可以用来找到类似问题的大O。既然是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) 输入 Online Encyclopedia of Integer Sequences，我通常会被带到一个包含模式的简单公式。

一旦您以这种方式作弊并找出规则，您就可以着手了解规则为何有效。

以下是我对 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。所以这是方法 getNumOfStepCombos 被自身调用的 3 * 5 == 15 倍。该方法也会从自身外部调用一次（来自 getPossibleStepCombination），因此调用总数为 3n + 1.

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

如果算法中有不属于 O(1) 的行，则不能直接使用此计数器方法，但您通常可以调整该方法。

Answer 2

保罗的回答在技术上没有错，但有点误导。我们应该通过函数如何响应输入大小的变化来计算大 O 表示法。保罗对 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。

如何计算动态规划（Memoization）算法的Big O

How to calculate Big O of Dynamic programming (Memoization) algorithm

java

algorithm

big-o

dynamic-programming