dynamic programming - what's the asymptotic runtime?
-
21-04-2021 - |
سؤال
I'm teaching myself dynamic programming. It's almost magical. But seriously. Anyway, the problem I worked out was : 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?
. The problem wasn't too hard, my implementation is below.
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);
}
}
However, now I want to get the runtime. How should I figure this out? I am familiar (and not much more) with Akra-Bazzi and Master Theorem. Do those apply here?
http://en.wikipedia.org/wiki/Master_theorem
Here it would seem that it could be: T(N) = 3 * T(???) + O(1)
but I'm really not sure.
thanks guys.
المحلول
In a worst case scenario analysis it would be:
T(N) = N * (containsKey(N) + 8)
Assuming that containsKey = N (it is probably N^2
or Log(N)
) then this simplifies to T(N) = N
.
You would have to find out the function for containsKey(N)
to get the actual equation.
You're really over thinking this though; you don't need to do a algorithm analysis for this. Good quote for you: "Premature optimization is the root of all evil"