Kurs:Algorithmen und Datenstrukturen/Vorlesung/Aufwandsanalyse von rekursiven Algorithmen
Aufwandsanalyse von rekursiven Algorithmen Bearbeiten
Auf dieser Seite wird der Aufwand von rekursiven Algorithmen untersucht.
public int fib(int n) {
if (n == 0 || n == 1) {
return 1;
} else {
return fib(n-1) + fib(n-2);
}
}
Wie ist nun der Aufwand für Fibonacci? Bei Rekursionsabbruch und im Rekursionsfall . Zur Bestimmung benutzen wir Rekursionsgleichungen.
Rekursionsgleichungen Bearbeiten
Eine Rekursionsgleichung ist eine Gleichung oder Ungleichung, die eine Funktion anhand ihrer Anwendung auf kleinere Werte beschreibt.
Rekursionsgleichung für Fibonacci:
Lösung von Rekursionsgleichungen Bearbeiten
Die Frage ist nun, welche Aufwandklasse T(n) beschreibt. Dies könnten alle möglichen Aufwandsklassen sein. Methoden um dieses Problem zu lösen, sind die vollständige Induktion und das Master-Theorem.
Spezialfall Divide and Conquer Algorithmus Bearbeiten
Ein Divide-and-Conquer Algorithmus stellt im Allgemeinen eine einfache, rekursive Version eines Algorithmus dar und hat drei Schritte:
- Divide: Unterteile das Problem in eine Zahl von Teilproblemen
- Conquer: Löse das Teilproblem rekursiv. Wenn das
Teilproblem klein genug ist, dann löse das Teilproblem direkt (z.B. bei leeren oder einelementigen Listen)
- Combine: Die Lösungen der Teilprobleme werden zu einer Gesamtlösung kombiniert.
Merge Sort ist beispielsweise ein Divide and Conquer Algorithmus.
- Divide: Zerteile eine Folge mit n Elementen in zwei Folgen mit je n/2 Elementen.
- Conquer: Wenn die resultierende Folge 1 oder 0 Elemente enthält, dann ist sie sortiert.Ansonsten wende Merge Sort rekursiv an.
- Combine: Mische die zwei sortierten Teilfolgen.
public List mergeSort(List f) {
if (f.size() <= 1) {
return f;
} else {
int m = f.size() / 2;
List left = mergeSort(f.subList(0,m));
List right = mergeSort(f.subList(m,f.size());
return merge(left, right);
}
}
Die dazugehörige Rekursionsgleichung lautet:
Im Allgemeinen ist die Rekursionsgleichung für Divide and Conquer Algorithmen:
mit D(n) als Aufwand für Divide, T(n/b) als Aufwand für Conquer und C(n) als Aufwand für Combine.
Ab- und Aufrunden Bearbeiten
Die Rekursionsgleichung von MergeSort beschreibt den Aufwand für den schlechtesten Fall.
Aber die Annahme, dass n eine geeignete ganze Zahl ist ergibt normalerweise das gleiche Ergebnis wie
eine beliebige Zahl mit Auf- bzw. Abrunden. Dies führt zur einfacheren Rekursionsgleichung:
Beispiel Binäre Suche Bearbeiten
public List binarySearch(ArrayList<Integer> f, int e) {
if (f.size() == 0) {
return -1;
} else {
int m = f.size() / 2;
if (f.get(m) == e) {
return m;
} else if (f.get(m) < e) {
return binarySearch(f.subList(0, m), e);
} else {
return binarySearch(f.subList(m+1, f.size()), e);
}
}
}
Die Rekursionsgleichung lautet
Literatur Bearbeiten
Da die Vorlesungsinhalte auf dem Buch Algorithmen und Datenstrukturen: Eine Einführung mit Java von Gunter Saake und Kai-Uwe Sattler aufbauen, empfiehlt sich dieses Buch um das hier vorgestellte Wissen zu vertiefen. Die auf dieser Seite behandelten Inhalte sind in Kapitel 7.3.4 zu finden.
