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.

Inhaltsverzeichnis

Mathematische Formulierung

Gegeben sei die Rekursionsgleichung

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

für eine Funktion 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;
  • ai und bi sind für alle i konstant, mit ai > 0 und 0 < bi < 1;
  • \left|g'(x)\right| \in O\left(x^c\right), wobei c eine Konstante ist und O das Landau-Symbol bezeichnet;
  • \left| h_i(x) \right| \in O\left(\frac{x}{(\log x)^2}\right) für alle i;
  • x0 ist eine Konstante.

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

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

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

Intuitiv ist hi(x) eine kleine Störung des Arguments von T. Wegen \lfloor b_i x \rfloor = b_i x + (\lfloor b_i x \rfloor - b_i x) und da \lfloor b_i x \rfloor - b_i x stets zwischen 0 und 1 ist, kann hi(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 T(n) = n + T \left(\frac{1}{2} n \right) und T(n) = n + T \left(\left\lfloor \frac{1}{2} n \right\rfloor \right) 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 ist, gegeben durch die Rekursionsgleichung

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 T(1) = 0. Somit lässt sich das Akra-Bazzi-Theorem anwenden, welches mit g(u) = u + 1 und k=2, a1 = a2 = 1, b1 = b2 = 1 / 2, zunächst p=1 und damit das asymptotische Verhalten

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.

Divide-and-Conquer mit ungleichen Teilproblemen

Sei T(n) definiert als 1 für 0 \leq n \leq 3 und 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 n > 3. Gemäß der Akra-Bazzi-Methode wird im ersten Schritt der Wert von p berechnet, so dass \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:


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).

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ä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.

Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Akra-Bazzi-Methode — 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 asymtotischen Analyse insbesondere von Divide and… …   Deutsch Wikipedia

  • Akra-Bazzi method — In computer science, the Akra Bazzi method, or Akra Bazzi theorem, is used to analyze the asymptotic behavior of the mathematical recurrences that appear in the analysis of divide and conquer algorithms where the sub problems have substantially… …   Wikipedia

  • Master theorem — For a result in enumerative combinatorics, see MacMahon Master theorem. In the analysis of algorithms, the master theorem provides a cookbook solution in asymptotic terms (using Big O notation) for recurrence relations of types that occur in the… …   Wikipedia

  • Master Theorem — Der Begriff Hauptsatz der Laufzeitfunktionen oder oft englisch Master Theorem, das ein Spezialfall des Akra Bazzi Theorems ist, bietet eine schnelle Lösung für die Frage, in welcher Laufzeitklasse eine gegebene rekursiv definierte Funktion liegt …   Deutsch Wikipedia

  • Master-Theorem — Der Begriff Hauptsatz der Laufzeitfunktionen oder oft englisch Master Theorem, das ein Spezialfall des Akra Bazzi Theorems ist, bietet eine schnelle Lösung für die Frage, in welcher Laufzeitklasse eine gegebene rekursiv definierte Funktion liegt …   Deutsch Wikipedia

  • Master-Method — Der Begriff Hauptsatz der Laufzeitfunktionen oder oft englisch Master Theorem, das ein Spezialfall des Akra Bazzi Theorems ist, bietet eine schnelle Lösung für die Frage, in welcher Laufzeitklasse eine gegebene rekursiv definierte Funktion liegt …   Deutsch Wikipedia

  • Master Method — Der Begriff Hauptsatz der Laufzeitfunktionen oder oft englisch Master Theorem, das ein Spezialfall des Akra Bazzi Theorems ist, bietet eine schnelle Lösung für die Frage, in welcher Laufzeitklasse eine gegebene rekursiv definierte Funktion liegt …   Deutsch Wikipedia

  • Mastertheorem — Der Begriff Hauptsatz der Laufzeitfunktionen oder oft englisch Master Theorem, das ein Spezialfall des Akra Bazzi Theorems ist, bietet eine schnelle Lösung für die Frage, in welcher Laufzeitklasse eine gegebene rekursiv definierte Funktion liegt …   Deutsch Wikipedia

  • List of mathematics articles (A) — NOTOC A A Beautiful Mind A Beautiful Mind (book) A Beautiful Mind (film) A Brief History of Time (film) A Course of Pure Mathematics A curious identity involving binomial coefficients A derivation of the discrete Fourier transform A equivalence A …   Wikipedia

  • List of combinatorics topics — This is a list of combinatorics topics.A few decades ago it might have been said that combinatorics is little more than a way to classify poorly understood problems, and some standard remedies. Great progress has been made since 1960.This page is …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”