Kurs:Algorithmen und Datenstrukturen/Vorlesung/Aufwandsanalyse von rekursiven Algorithmen




Aufwandsanalyse von rekursiven AlgorithmenBearbeiten

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.

RekursionsgleichungenBearbeiten

Eine Rekursionsgleichung ist eine Gleichung oder Ungleichung, die eine Funktion anhand ihrer Anwendung auf kleinere Werte beschreibt.

Rekursionsgleichung für Fibonacci:

 

Lösung von RekursionsgleichungenBearbeiten

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 AlgorithmusBearbeiten

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 AufrundenBearbeiten

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 SucheBearbeiten

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  

LiteraturBearbeiten

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.