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

10

Angenommen, ein Algorithmus hat eine Laufzeitwiederholungsbeziehung:

T(n)={g(n)+T(n1)+T(δn):nn0f(n):n<n0

für eine Konstante . Angenommen, ist in polynomisch , vielleicht quadratisch. Am wahrscheinlichsten ist in exponentiell .g n f n0<δ<1gnfn

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

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)=aT(n/a)+g(n)
1
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? fn0f
Raphael
Der Parameter kann sein. Es wäre schön zu sehen, wie die Laufzeit von abhängt . n 0n0n0
Austin Buchanan
1
Ich habe eine verwandte Frage gestellt , die bisher keinen allgemeinen Satz für Wiederholungen dieser Art hervorgebracht hat.
Raphael

Antworten:

5

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(n1)T(n)T(n)

T(n)=T(δn)+g(n).
t(x)=t(δx)+g(x),
ddxt(x)=t(δ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)
Informiert