動的プログラミング - 漸近的なランタイムは何ですか？

Question

私はダイナミックプログラミングを教えています。それはほぼ魔法のようです。しかし、真剣に。とにかく、私が取り組んだ問題は：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)が、私は本当にわかりません。

ありがとうございます。最悪の場合のシナリオ分析で

Answer 1

それは次のようになります

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

ことのcontainsKeyを仮定= N（それはおそらくN^2又はLog(N)である）、これはT(N) = Nを簡素化します。

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

あなたは本当にこれを考えています。このためにアルゴリズム分析を行う必要はありません。良い見積もり：「時期尚早な最適化はすべての悪の根源です」