动态规划——什么是渐近运行时？

Question

我正在自学动态编程。这几乎是神奇的。但说真的。无论如何，我解决的问题是：给定一个有 N 级台阶的楼梯和一个可以一次走 1、2 或 3 步的孩子，孩子可以通过多少种不同的方式到达顶层？.问题不太难，我的实现如下。

import java.util.HashMap;

public class ChildSteps {
    private HashMap<Integer, Integer> waysToStep;

    public ChildSteps() {
        waysToStep = new HashMap<Integer, Integer>();
    }

    public int getNthStep(int n) {
        if (n < 0) return 0; // 0 ways to get to a negative step

        // Base Case
        if (n == 0) return 1;

        // If not yet memorized
        if (!waysToStep.containsKey(n)) {
            waysToStep.put(n, getNthStep(n - 3) + getNthStep(n - 2) + getNthStep(n - 1));
        }

        return waysToStep.get(n);
    }
}

但是，现在我想获取运行时。我该如何解决这个问题？我熟悉（但不多）Akra-Bazzi 和 Master Theorem。这些适用于此吗？

http://en.wikipedia.org/wiki/Master_theorem

这里看起来可能是： T(N) = 3 * T(???) + O(1) 但我真的不确定。

谢谢你们。

Answer 1

在最坏的情况分析中，它会是：

T(N) = N * (containsKey(N) + 8)

假设 containsKey = N（可能是 N^2 或 Log(N)），那么这将简化为 T (N) = N。

您必须找出 containsKey(N) 的函数才能得到实际的方程。

不过你真的想多了；您不需要为此进行算法分析。适合您的名言：“过早的优化是万恶之源”