динамическое программирование - что такое асимптотическое время выполнения? - PullRequest
Новая
       21

динамическое программирование - что такое асимптотическое время выполнения?

1 голос
/ 02 февраля 2012

Я учу себя динамическому программированию. Это почти волшебно. Но серьезно. Во всяком случае, проблема, которую я разработал, была: 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 теоремой. Это применимо здесь?

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

Здесь может показаться, что это может быть: T(N) = 3 * T(???) + O(1), но я действительно не уверен.

спасибо, ребята.

1 Ответ

1 голос
/ 02 февраля 2012

В анализе сценариев наихудшего случая это будет: 

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

Если предположить, что содержит Ключ = N (это, вероятно, N^2 или Log(N)), тогда это упрощается до T(N) = N.

Вам нужно найти функцию для containsKey(N), чтобы получить реальное уравнение.

Хотя вы действительно слишком задумываетесь над этим;вам не нужно делать анализ алгоритма для этого.Хорошая цитата для вас: «Преждевременная оптимизация - корень зла»

...