java - 如何计算动态规划(Memoization)算法的Big O

Question

我将如何计算 DP 算法的大 O。我开始意识到我计算算法的方法并不总是有效。我会使用简单的技巧来提取 Big O 是什么。例如，如果我正在评估下面算法的无内存版本(删除缓存机制)，我会查看递归方法在这种情况下调用自身的次数 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 引用是否为 空。这些东西都是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 给出。

在更复杂的示例中，我可能无法发现模式，因此我将前几个数字(例如 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 开始时，我们运行该行 exacly 5 次；一次为 n == 5，一次为 n == 4，一次为 n == 3，一次为 n == 2 和一次 n == 1。所以这是从自身调用方法 getNumOfStepCombos 的 3 * 5 == 15 次。该方法也会从自身外部调用一次(来自 getPossibleStepCombination)，因此调用总数为 3n + 1。

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

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