imported>Aka: /* Quellen */ Halbgeviertstrich

2018-07-11T21:14:04Z

Quellen: Halbgeviertstrich

Neue Seite

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

== Mathematische Formulierung ==
Gegeben sei die Rekursionsgleichung

:<math>T(x)=g(x) + \sum_{i=1}^k a_i T(b_i x + h_i(x)) </math>     für <math>x \geq x_0,</math>

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

* Es sind genügend Basisfälle vorhanden, so dass die Gleichung eindeutig lösbar ist;
* <math>a_i</math> und <math>b_i</math> sind für alle ''i'' konstant, mit <math>a_i > 0</math> und <math>0 < b_i < 1</math>;
* <math>\left|g'(x)\right| \in O\left(x^c\right)</math>, wobei ''c'' eine Konstante ist und ''O'' das [[Landau-Symbol]] bezeichnet;
* <math>\left| h_i(x) \right| \in O\left(\frac{x}{(\log x)^2}\right)</math> für alle ''i'';
* <math>x_0</math> ist eine Konstante.

Dann gilt für das asymptotische Verhalten von ''T''(''x'') die Abschätzung in der [[Landau-Symbol|Theta-Notation]]

:<math>T(x) \in \Theta \left( x^p\left( 1+\int_1^x \frac{g(u)}{u^{p+1}} \, \mathrm{d}u \right)\right)</math>

mit <math>p \in \mathbb{R}^+</math>, so dass <math>\sum_{i=1}^k a_i b_i^p = 1.</math>

Intuitiv ist <math>h_i(x)</math> eine kleine Störung des Arguments von ''T''. Wegen <math>\lfloor b_i x \rfloor = b_i x + (\lfloor b_i x \rfloor - b_i x)</math> und da <math>\lfloor b_i x \rfloor - b_i x</math> stets zwischen 0 und 1 ist, kann <math>h_i(x)</math> 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 <math>T(n) = n + T \left(\frac{1}{2} n \right)</math> und <math>T(n) = n + T \left(\left\lfloor \frac{1}{2} n \right\rfloor \right)</math> gemäß dem Akra-Bazzi-Theorem dasselbe asymptotische Verhalten.

== Beispiele ==
=== Mergesort ===
Für den [[Mergesort]] ist die erforderliche Anzahl ''T''(''n'') von Vergleichen, die näherungsweise proportional zu dessen [[Laufzeit (Informatik)|Laufzeit]] ist, gegeben durch die Rekursionsgleichung

:<math>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</math>

mit dem Basisfall <math>T(1) = 0</math>. Somit lässt sich das Akra-Bazzi-Theorem anwenden, welches mit <math>g(u) = u+1</math> und ''k''=2, <math>a_1=a_2=1,</math> <math>b_1=b_2=1/2</math>, zunächst ''p''=1 und damit das asymptotische Verhalten

::<math>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)</math>

ergibt.

=== Divide-and-Conquer mit ungleichen Teilproblemen ===
Sei <math>T(n)</math> definiert als 1 für <math>0 \leq n \leq 3</math> und <math>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)</math> für <math>n > 3</math>. Gemäß der Akra-Bazzi-Methode wird im ersten Schritt der Wert von ''p'' berechnet, so dass <math>\frac{7}{4} \left(\frac{1}{2}\right)^p + \left(\frac{3}{4} \right)^p = 1</math>. Das ergibt hier ''p'' = 2. Im zweiten Schritt wird das asymptotische Verhalten nach der Formel berechnet:

:<math>
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).
</math>

== Bedeutung ==
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ät (Informatik)|Komplexitätsbetrachtung]] rekursiver Algorithmen verwendet, insbesondere von Divide-and-Conquer-Algorithmen.

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

*Tom Leighton: [http://citeseer.ist.psu.edu/252350.html Notes on Better Master Theorems for Divide-and-Conquer Recurrences], Manuscript. Massachusetts Institute of Technology, 1996.

[[Kategorie:Rekursion]]
[[Kategorie:Komplexitätstheorie]]

Akra-Bazzi-Theorem - Versionsgeschichte

imported>Aka: /* Quellen */ Halbgeviertstrich