Asymptotische Approximation einer Wiederholungsbeziehung (Akra-Bazzi scheint nicht zuzutreffen)

Angenommen, ein Algorithmus hat eine Laufzeitwiederholungsbeziehung:

$T(n) = \left\{ \begin{array}{lr} g(n)+T(n-1) + T(\lfloor\delta n\rfloor ) & : n \ge n_0\\ f(n) & : n < n_0 \end{array} \right.$

für eine Konstante . Angenommen, ist in polynomisch , vielleicht quadratisch. Am wahrscheinlichsten ist in exponentiell . $0 < \delta < 1$ $g$ $n$ $f$ $n$

Wie würde man die Laufzeit analysieren ( wäre ausgezeichnet)? Der Hauptsatz und die allgemeinere Akra-Bazzi-Methode scheinen nicht zuzutreffen. $\Theta$

asymptotics recurrence-relation Austin Buchanan
quelle

Eine gute Untergrenze zu finden ist einfach, aber eine gute Obergrenze zu finden ist schwierig, aber grob gesagt scheint es nahe an .

T (n) = a \cdot T (n / a) + g (n)

$T(n) = a\cdot T(n/a) + g(n)$

Wenn Sie noch nach einer Antwort suchen, sollten Sie Graham, Knuth und Patashnik, "Concrete Mathematics", überprüfen.

Kaveh

Unter der Annahme, dass konstant ist, brauchen wir keine Annahmen für , oder?

n_{0}

$n_0$

f

$f$

Raphael

Der Parameter kann sein. Es wäre schön zu sehen, wie die Laufzeit von abhängt .

n_{0}

$n_0$

n_{0}

$n_0$

Austin Buchanan

Ich habe eine verwandte Frage gestellt , die bisher keinen allgemeinen Satz für Wiederholungen dieser Art hervorgebracht hat.

Raphael

Antworten:

Ein möglicher Ansatz könnte analog zu Differentialgleichungen sein. Sei . Hier ist ein diskretes Analogon der ersten Ableitung von . Wir erhalten die folgende Beziehung: Das kontinuierliche Analogon davon ist die Differentialgleichung oder, wenn Sie es lieber anders sehen möchten: Das ist eine Differentialgleichung. $T'(n) = T(n)-T(n-1)$ $T'(n)$ $T(n)$

T^{'} (n) = T (⌊ δ n ⌋) + g (n) .

$T'(n) = T(\lfloor \delta n \rfloor) + g(n).$

t^{'} (x) = t (δ x) + g (x),

$t'(x) = t(\delta x) + g(x),$

\frac{d}{d x} t (x) = t (δ x) + g (x) .

${d \over dx} t(x) = t(\delta x) + g(x).$

Nun könnten Sie versuchen, die Differentialgleichung für die stetige Funktion zu lösen , dann die Hypothese aufstellen, dass eine ähnliche Funktion die Lösung für Ihre ursprüngliche Wiederholungsbeziehung ist, und versuchen, Ihre Hypothese zu beweisen. Zumindest ist dies ein allgemeiner Ansatz, dem Sie folgen könnten. $t(x)$

Ich habe alles vergessen, was ich einmal über Differentialgleichungen wusste, daher kenne ich die Lösung dieser Differentialgleichung nicht, aber vielleicht können Sie sie lösen, indem Sie alle Techniken zum Lösen von Differentialgleichungen überprüfen.

DW
quelle

Donald J Newman scheint diese Technik oft angewendet zu haben, mit großartigen Ergebnissen.

Aryabhata

Ohne weiter zu suchen. Es ist nicht einfach, diese Differentialgleichung zu lösen. Ich bin nicht allzu überzeugt, dass es eine geschlossene Formlösung gibt, nachdem ich einige Grundformen für ausprobiert habe .

t (x)

$t(x)$

Informiert