動態編程 - 什麼是漸近運行時？

我在教自己動態編程。這幾乎是神奇的。不過實話說。無論如何，我制定的問題是：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和主定理很熟悉（也沒有更多）。這些適用於這裏嗎？

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

這似乎它可能是：T(N) = 3 * T(???) + O(1)，但我真的不知道。

謝謝你們。

來源

2012-02-02 lollercoaster

你有沒有爲此首先計算出數學公式？ – 2012-02-02 02:17:53

不，我真的不知道如何。一個等式，究竟是什麼？ – lollercoaster 2012-02-02 02:20:20

給定N個步驟，如果您一次可以分多步，可以有多少種不同的方法到達頂端。一旦你知道了方程，那麼你已經成爲一個微不足道的問題。 – 2012-02-02 02:23:49

在最壞的情況下分析這將是：

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

假設的containsKey = N（它可能是N^2或Log(N)），那麼這簡化爲T(N) = N。

您將不得不找出containsKey(N)的函數來獲得實際方程。

你真的在想這個，你不需要爲此做一個算法分析。給你的好消息：「不成熟的優化是所有邪惡的根源」

來源

2012-02-02 02:34:11

你能解釋一下你如何去這條線：'T（N）= N *（containsKey（N）+ 8）'？是的，我沒有真正優化，我只是想學習如何計算漸近運行時間。 – lollercoaster 2012-02-03 16:06:11

動態編程 - 什麼是漸近運行時？

回答

相關問題