Algorithmen

Das Master-Theorem

Wenn wir es mit rekursiven Funktionen zu tun haben, dann nutzen wir das Master Theorem, um eine Laufzeitabschätzung zu bekommen. Gerade bei Divide & Conquer Algorithmen ist dies sehr nützlich. Doch wie arbeitet man mit diesem Theorem?

Gegeben Sei eine Funktion wie diese:

Master-theorem-rekursive-funktion

Diese Funktion bedeutet eigentlich nur: Wir haben ein Problem mit n Datensätzen, teilen dieses Hauptproblem in a Unterprobleme der Größe n / b und die Kosten für die Teilung und das Zusammenführen ist f(n). Wichtig dabei ist, dass f(n) eine positive Funktion sein soll.

Der erste Schritt, den wir machen, wenn wir so eine Funktion gegeben haben, ist folgendes zu berechnen:

Master-theorem-erster-schritt

Ist u berechnet worden, gilt es drei Fälle zu beachten.

Fall 1

Wenn für ein Epsilon > 0 gilt:

master-theorem-fall-eins

Dann gilt für T(n):
Master-theorem-erster-schritt-2

Fall 2

Wenn gilt:
master-theorem-fall-2

Dann gilt für T(n):
master-theorem-fall-2-2

Fall 3

Wenn für ein Epsilon > 0 und ein c < 1 gilt: master-theorem-fall-3

master-theorem-fall-3-2

Dann gilt für T(n):
master-theorem-fall-3-3

Beispiel

Dies ist jetzt unsere Beispielfunktion:

master-theorem-beispiel-1

Wir schreiben die Werte erst einmal heraus:
master-theorem-beispiel-2

Und berechnen u:
master-theorem-beispiel.3

Wir sehen, u ist kleiner als 2. Also tritt der dritte Fall auf. Nun müssen wir noch prüfen, ob die Bedingung gilt:
master-theorem-fall-3-2

Wir setzen also ein:
master-theorem-beispiel-4

Formen um:
master-theorem-beispiel-5

Und bekommen heraus:
master-theorem-beispiel-6

So lang wir unser c also zwischen 3/4 und 1 wählen (die 1 ausgenommen), gilt dir Bedingung und wir können die Laufzeitschätzung der rekursiven Funktion benennen.

Falls ihr noch fragen habt, könnt ihr sie gerne stellen. Ich hoffe jedoch, dass das euch schon etwas Licht ins Dunkle gebracht hat.

3 Gedanken zu „Das Master-Theorem

  1. Schöne Zusammenfassung, aber ich habe noch eine Frage: kann ich das Epsilon so wählen wie ich möchte, also epsilon > 0 nach meiner Wahl? Sagen wir einmal epsilon = 42, wenn dadurch die Klasse korrekt wird?

Schreibe einen Kommentar zu Epsilon Antworten abbrechen

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.