Akra-Bazzi-Theorem

In der Informatik dient das Akra-Bazzi-Theorem, oder auch die Akra-Bazzi-Methode, dazu, das asymptotische Verhalten von Lösungen mathematischer Rekursionsgleichungen zu bestimmen, die bei der asymptotischen Analyse insbesondere von Divide-and-Conquer-Algorithmen auftreten. Es wurde 1998 veröffentlicht und ist eine Verallgemeinerung des Master-Theorems, das nur auf diejenigen Divide-and-Conquer-Algorithmen angewandt werden kann, deren Teilprobleme gleiche Größe haben.

Gegeben sei die Rekursionsgleichung

${\displaystyle T(x)=g(x)+\sum _{i=1}^{k}a_{i}T(b_{i}x+h_{i}(x))}$     für ${\displaystyle x\geq x_{0},}$

für eine Funktion ${\displaystyle T:\mathbb {R} ^{+}\to \mathbb {R} ^{+}}$, so dass die folgenden Bedingungen erfüllt sind:

• Es sind genügend Basisfälle vorhanden, so dass die Gleichung eindeutig lösbar ist;
• ${\displaystyle a_{i}}$ und ${\displaystyle b_{i}}$ sind für alle i konstant, mit ${\displaystyle a_{i}>0}$ und ${\displaystyle 0<b_{i}<1}$;
• ${\displaystyle \left|g'(x)\right|\in O\left(x^{c}\right)}$, wobei c eine Konstante ist und O das Landau-Symbol bezeichnet;
• ${\displaystyle \left|h_{i}(x)\right|\in O\left({\frac {x}{(\log x)^{2}}}\right)}$ für alle i;
• ${\displaystyle x_{0}}$ ist eine Konstante.

Dann gilt für das asymptotische Verhalten von T(x) die Abschätzung in der Theta-Notation

${\displaystyle T(x)\in \Theta \left(x^{p}\left(1+\int _{1}^{x}{\frac {g(u)}{u^{p+1}}}\,\mathrm {d} u\right)\right)}$

mit ${\displaystyle p\in \mathbb {R} ^{+}}$, so dass ${\displaystyle \sum _{i=1}^{k}a_{i}b_{i}^{p}=1.}$

Intuitiv ist ${\displaystyle h_{i}(x)}$ eine kleine Störung des Arguments von T. Wegen ${\displaystyle \lfloor b_{i}x\rfloor =b_{i}x+(\lfloor b_{i}x\rfloor -b_{i}x)}$ und da ${\displaystyle \lfloor b_{i}x\rfloor -b_{i}x}$ stets zwischen 0 und 1 ist, kann ${\displaystyle h_{i}(x)}$ dazu benutzt werden, die Gauß-Klammer ("Floor-Funktion") im Argument zu ignorieren. Ähnlich kann man für die Irrelevanz der Aufrundungsfunktion ("Ceiling-Funktion") für das asymptotische Verhalten von T argumentieren. Beispielsweise haben ${\displaystyle T(n)=n+T\left({\frac {1}{2}}n\right)}$ und ${\displaystyle T(n)=n+T\left(\left\lfloor {\frac {1}{2}}n\right\rfloor \right)}$ gemäß dem Akra-Bazzi-Theorem dasselbe asymptotische Verhalten.

Für den Mergesort ist die erforderliche Anzahl T(n) von Vergleichen, die näherungsweise proportional zu dessen Laufzeit ist, gegeben durch die Rekursionsgleichung

${\displaystyle T(n)=T\left(\left\lfloor {\frac {1}{2}}n\right\rfloor \right)+T\left(\left\lceil {\frac {1}{2}}n\right\rceil \right)+n+1}$

mit dem Basisfall ${\displaystyle T(1)=0}$. Somit lässt sich das Akra-Bazzi-Theorem anwenden, welches mit ${\displaystyle g(u)=u+1}$ und k=2, ${\displaystyle a_{1}=a_{2}=1,}$ ${\displaystyle b_{1}=b_{2}=1/2}$, zunächst p=1 und damit das asymptotische Verhalten

${\displaystyle T(n)\in \Theta \left(n\left(1+\int _{1}^{n}{\frac {u+1}{u^{2}}}\,\mathrm {d} u\right)\right)=\Theta \left(n\left(\ln n+{\frac {1}{n}}\right)\right)=\Theta (n\,\log n)}$

ergibt.

Sei ${\displaystyle T(n)}$ definiert als 1 für ${\displaystyle 0\leq n\leq 3}$ und ${\displaystyle n^{2}+{\frac {7}{4}}T\left(\left\lfloor {\frac {1}{2}}n\right\rfloor \right)+T\left(\left\lceil {\frac {3}{4}}n\right\rceil \right)}$ für ${\displaystyle n>3}$. Gemäß der Akra-Bazzi-Methode wird im ersten Schritt der Wert von p berechnet, so dass ${\displaystyle {\frac {7}{4}}\left({\frac {1}{2}}\right)^{p}+\left({\frac {3}{4}}\right)^{p}=1}$. Das ergibt hier p = 2. Im zweiten Schritt wird das asymptotische Verhalten nach der Formel berechnet:

${\displaystyle T(x)\in \Theta \left(x^{p}\left(1+\int _{1}^{x}{\frac {g(u)}{u^{p+1}}}\,\mathrm {d} u\right)\right)=\Theta \left(x^{2}\left(1+\int _{1}^{x}{\frac {u^{2}}{u^{3}}}\,\mathrm {d} u\right)\right)=\Theta (x^{2}(1+\ln x))=\Theta (x^{2}\log x).}$

Das Akra-Bazzi-Theorem umfasst eine sehr weite Klasse von Rekursionsgleichungen und verallgemeinert wesentlich zuvor bekannte Sätze zur Bestimmung von asymptotischem Verhalten. Vorwiegend wird es für die Komplexitätsbetrachtung rekursiver Algorithmen verwendet, insbesondere von Divide-and-Conquer-Algorithmen.

• Mohamad Akra, Louay Bazzi: On the solution of linear recurrence equations. Computational Optimization and Applications 10(2), 1998, pp. 195–210.

• Tom Leighton: Notes on Better Master Theorems for Divide-and-Conquer Recurrences, Manuscript. Massachusetts Institute of Technology, 1996.