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:

  1. Divide: Unterteile das Problem in eine Zahl von Teilproblemen
  2. 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)

  1. Combine: Die Lösungen der Teilprobleme werden zu einer Gesamtlösung kombiniert.

Merge Sort ist beispielsweise ein Divide and Conquer Algorithmus.

  1. Divide: Zerteile eine Folge mit n Elementen in zwei Folgen mit je n/2 Elementen.
  2. Conquer: Wenn die resultierende Folge 1 oder 0 Elemente enthält, dann ist sie sortiert.Ansonsten wende Merge Sort rekursiv an.
  3. 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.