1

私は動的プログラミングを独学しています。それはほとんど魔法です。しかし、真剣に。とにかく、私が解決した問題は次のとおりGiven a stairs of N steps and a child who can either take 1, 2, or 3 steps at a time, how many different ways can the child reach the top step?です。問題はそれほど難しくありませんでした。私の実装は以下のとおりです。

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)しかし、私にはよくわかりません。

みんなありがとう。

4

1 に答える 1

1

最悪のシナリオ分析では、次のようになります。

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

N^2containsKey = N (おそらくまたは)であると仮定するとLog(N)、これは に単純化されT(N) = Nます。

containsKey(N)実際の方程式を得るには、関数を見つける必要があります。

しかし、あなたは本当にこれを考えすぎています。このためにアルゴリズム分析を行う必要はありません。あなたへの良い引用: 「時期尚早の最適化は諸悪の根源です」

于 2012-02-02T02:34:11.173 に答える