In der Informatik wird die Akra-Bazzi Methode oder Akra-Bazzi Lehrsatz, verwendet, um das asymptotische Verhalten der mathematischen Wiederauftreten zu analysieren, die in der Analyse dessen erscheinen, teilen und überwinden Algorithmen, wo die Teilprobleme wesentlich verschiedene Größen haben. Es ist eine Generalisation des wohl bekannten Master-Lehrsatzes, der annimmt, dass die Teilprobleme gleiche Größe haben.

Die Formel

Die Akra-Bazzi Methode gilt für Wiederauftreten-Formeln der Form

:

Die Bedingungen für den Gebrauch sind:

• genügend Grundfälle werden zur Verfügung gestellt

• und sind Konstanten für alles ich

• für alles ich

• wo c eine Konstante ist und O Große O Notation in Notenschrift schreibt

für alles ich

• ist ein unveränderlicher

Das asymptotische Verhalten von T (x) wird durch die Bestimmung des Werts von p gefunden für der und das Einstecken schätzen die in die Gleichung

:

(sieh Θ). Intuitiv, vertritt eine kleine Unruhe im Index von T. Durch die Anmerkung, dass und das immer zwischen 0 und 1 ist, kann verwendet werden, um die Fußboden-Funktion im Index zu ignorieren. Ähnlich kann man auch die Decke-Funktion ignorieren. Zum Beispiel, und, laut des Akra-Bazzi Lehrsatzes, wird dasselbe asymptotische Verhalten haben.

Ein Beispiel

Denken Sie wird als 1 für ganze Zahlen und für ganze Zahlen definiert. In der Verwendung der Akra-Bazzi Methode ist der erste Schritt, den Wert von p für der zu finden. In diesem Beispiel, p = 2. Dann, mit der Formel, kann das asymptotische Verhalten wie folgt bestimmt werden:

:\begin {richten }\aus

T (x) & \in \Theta \left (x^p\left (1 +\int_1^x \frac {g (u)} {U^ {p+1} }\\, du \right) \right) \\

& = \Theta \left (X^2 \left (1 +\int_1^x \frac {u^2} {u^3 }\\, du \right) \right) \\

& = \Theta (x^2 (1 + \ln x)) \\

& = \Theta (X^2 \log x).

\end {richten }\aus</Mathematik>

Bedeutung

Die Akra-Bazzi Methode ist nützlicher als die meisten anderen Techniken, um asymptotisches Verhalten zu bestimmen, weil es solch ein großes Angebot an Fällen bedeckt. Seine primäre Anwendung ist die Annäherung der Durchlaufzeit von vielen teilen-und-überwinden Algorithmen. Zum Beispiel, in der Verflechtungssorte, hat die Zahl von Vergleichen im Grenzfall verlangt, der zu seiner Durchlaufzeit grob proportional ist, wird rekursiv und als gegeben

:

für ganze Zahlen, und kann so mit der Akra-Bazzi Methode geschätzt werden zu sein.

• Mohamad Akra, Louay Bazzi: Auf der Lösung geradliniger Wiederauftreten-Gleichungen. Rechenbetonte Optimierung und Anwendungen 10 (2):195-210, 1998.
• Tom Leighton: Zeichen auf Besseren Master-Lehrsätzen für Teilen-und-überwinden Wiederauftreten, Manuskript. Institut von Massachusetts für die Technologie, 1996, 9 Seiten.
• Beweis und Anwendung auf wenigen Beispielen