Kurs:Algorithmen und Datenstrukturen (hsrw)/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.
