Ich habe eine Rekursionsbeziehung, die die Laufzeit eines unbekannten Algorithmus modelliert, und ich muss entweder die untere Grenze der Laufzeit dieses Algorithmus oder die obere und untere Grenze finden.Asymptotische Analyse einer Wiederholungsrelation
Pardon die grobe Formating; der Latex-zu-Bild-Parser Ich habe seltsamerweise Zahlengleichungen benutzt: Die Zahl für jede Gleichung ist unten und links des Markups, auf das sich die Zahl bezieht.
Die Gleichungen (1) und (2) sind die Teile der Rekursionsbeziehung.
Um von Gleichung (2) zu (3) zu gelangen, schreibe ein paar Wiederholungen der Wiederholung aus und beobachte das Muster, das sich bildet - verallgemeinere es dann mit der neuen Variablen k.
Beachten Sie, dass diese Wiederholung stoppt, wenn Gleichung (4) wahr ist.
Die Gleichung (4) in Gleichung (3) ersetzen, um die Gleichung (5) zu erhalten. Verwenden Sie auch die Logarithmus-Basisformeländerung, um alle Logs in Bezug auf Base 2 zu erhalten.
Von Gleichung (5) zu Gleichung (6) Ich versuche, einige Beobachtung über Gleichung (5) in Bezug auf Big-Oh-Analyse zu machen. Aber ehrlich gesagt ist dieser letzte Schritt nur eine Vermutung von meiner Seite.
Angenommen Gleichung (5) ist wahr, wie würde ich das Theta, Omega oder Oh der Gleichung (5) ausdrücken, und - am wichtigsten - wie würde man es beweisen?
Mein Gedanke war - wir sind daran interessiert, das Verhalten der Gleichung (5) zu kennen, da n sehr, sehr groß wird. Aber die Grenze von Gleichung (5), wenn n gegen unendlich geht, beinhaltet den Logarithmus einer negativen Zahl, die - eine Sackgasse und wahrscheinlich falsch ist.
Jede Hilfe wird geschätzt.
Sie können das Ergebnis mit dem [Master-Theorem] (https://en.wikipedia.org/wiki/Master_theorem) erhalten. – AbcAeffchen