Kurs:Algorithmen und Datenstrukturen (hsrw)/Vorlesung/Aufwandsanalyse von iterativen Algorithmen

Aufwandsanalyse von iterativen Algorithmen

Auf dieser Seite wird der Aufwand von iterativen Algorithmen analysiert. Als Aufwand wird die Anzahl der durchlaufenen Operationen zur Lösung des Problems bezeichnet ( Zuweisungen, Vergleiche...). Häufig ist der Aufwand abhängig vom Eingabeparameter (Problemgröße). Die Aufwandsklasse sagt, wie der Aufwand in Abhängigkeit von der Problemgröße wächst. Doch wie kann man nun bei beliebigem Java Code die Aufwandsklasse bestimmen?

Aufwand von Programmen ablesen

void alg1(int n){
     int m = 2;
     int i;
     int k = n;
     while (n > 0){
         i = k;
         while (i > 0) {
               m = m + i;
               i = i / 2;
         }
         n = n - 1;
    }
}

Die Aufwandsklasse ist $O(n\cdot log~n)$ . Die äußere Schleife wird n-mal durchlaufen und die Innere Schleife log n-mal.

void alg1(int n) {
      int m = 1;
      int i = 0;
      while (m < n) {
         while (i < m) 
              i = i + 1;
      m = m + i;
      }
}

Hier ist die Aufwandsklasse O(n+log n). In jedem Durchlauf der äußeren Schleife wird m verdoppelt, d.h. sie läuft log n Mal. Die innere Schleife läuft bis n/2, aber nicht jedes Mal, weil i nur ein Mal auf 0 gesetzt wird. Man könnte als Aufwandsklasse auch O(n) sagen, da der Summand log n nicht ins Gewicht fällt.

Bestandteile iterativer Algorithmen

Zum einen haben wir elementare Anweisungen wie Zuweisungen und Vergleiche. Diese haben einen Aufwand von 1.

Des Weiteren haben wir Sequenzen $\alpha _{1}~und~\alpha _{2}$ oder auch $\alpha _{1};\alpha _{2}$ geschrieben. Die obere Grenze ist $O(f_{\alpha _{1}}(n))+O(f_{\alpha _{2}}(n))$ und die untere Grenze ist $\Omega (f_{\alpha _{1}}(n))+\Omega (f_{\alpha _{2}}(n))$ . Dabei ist $f_{\alpha _{1}}(n)$ der Aufwand, der bei der Ausführung von $\alpha _{1}$ entsteht.

Ein weiterer Bestandteil ist die Selektion. $if(B)\{\alpha _{1}\}else\{\alpha _{2}\}$ . Hier ist die obere Grenze $O(f_{B}(n))+O(max(f_{\alpha _{1}}(n),f_{\alpha _{2}}(n)))$ und die untere Grenze $\Omega (f_{B}(n))+\Omega (min(f_{\alpha _{1}}(n),f_{\alpha _{2}}(n)))$ .

Außerdem haben wir Iterationen $while(B)\{\alpha \}$ . Hierbei ist die obere und die untere Grenze die Anzahl der Schleifendurchläufe, $(O(f_{B}(n))+O(f_{\alpha }(n)))$ und die untere Grenze $(\Omega (f_{B}(n))+\Omega (f_{\alpha }(n)))$ . Doch wie ist der Aufwand für eine for-Schleife? Ein Beispiel ist $for(\alpha _{1};B;\alpha _{2})\{\alpha _{3}\}$ . Die Antwort ist die Abbildung auf eine while-Schleife.

$\alpha _{1};$

while(B) {

$\alpha _{3};$

$\alpha _{2};$

}

Beispiel Sequenz

public int berechne(int n) {
  int x = 0;
  x = x + 1;
  return x;
}

Jede Zeile hat den Aufwand $\Theta (1)$ . Wie viele Operationen werden nun durchlaufen? Und ist die Anzahl abhängig vom Eingabeparameter? Der Aufwand ist $f(n)=\Theta (1)+\Theta (1)+\Theta (1)=3\cdot \Theta (1)$

Die Aufwandsklasse ist somit $\Theta (f(n))=\Theta (1)$

Beispiel Schleifen

public int berechne(int n) {
  int x = 0;
  for (int i=0; i < n; i++) {
    x = x + 1;
  }
  return x;
}

Die for Schleife hat den Aufwand $n\cdot \Theta (1)$ . Die Initialisierung und das return haben jeweils den Aufwand $\Theta (1)$ .

Der Gesamtaufwand ist somit $f(n)=\Theta (1)+n\cdot \Theta (1)+\Theta (1)=2\cdot \Theta (1)+\Theta (n)$ . Somit ist die Aufwandsklasse $\Theta (f(n))=\Theta (n)$ .

public int berechne(int n) {
  int x = 0;
  for (int i=0; i < n; i++) {
    for (int j=0; j < n; j++) {
      x = x + 1;
    }
  }
  return x;
}

Hier hat die for-Schleife den Aufwand $n\cdot (n\cdot \Theta (1))$ und die Initialisierung und das return wieder $\Theta (1)$ . Damit ergibt der sich Gesamtaufwand $f(n)=\Theta (1)+n^{2}\cdot \Theta (1)+\Theta (1)=2\cdot \Theta (1)+\Theta (n^{2})$ . Daraus folgt die Aufwandsklasse $\Theta (f(n))=\Theta (n^{2})$ .

Beispiel Selektion

public int berechne(int n) { 
   if (n % 2 == 0) { 
      int x = 0;
      for (int i=0; i < n; i++) { 
         x = x + 1; 
      }
      return x;
   }else{
      return n;
   }
}

Hier hat die for-Schleife einen Aufwand von $\Theta (n)$ . Die Initialisierung und das return wieder $\Theta (1)$ .

Die obere Grenze ist somit $O(f(n))=\Theta (1)+O(max(\Theta (n),\Theta (1))=O(n)$ und die untere Grenze $\Omega (f(n))=\Theta (1)+\Omega (min(\Theta (n),\Theta (1))=\Omega (1)$

Faustregeln

Zu den häufig verwendeten Faustregeln gehört, dass wenn wir keine Schleife haben, der Aufwand konstant ist. Eine weitere ist, dass bei einer Schleife immer ein linearer Aufwand vorliegt. Bei zwei geschachtelten Schleifen haben wir immer einen quadratischen Aufwand. Doch die Faustegeln gelten nicht ohne Ausnahmen. Besonders Acht geben muss man bei Aufwandsbestimmungen für Schleifen, bei mehreren Eingabevariablen, bei Funktionsaufrufen und bei Rekursionen.

Aufwandsbestimmung für Schleifen

public int berechne(int n) { 
  int x = 0; 
  for (int i=0; i < 5; i++) { 
    x = x + 1; 
  } 
  return x; 
}

Der Schleifenabbruch hängt nicht vom Eingabeparameter ab. Der Aufwand beträgt $f(n)=\Theta (1)+5\cdot \Theta (1)+\Theta (1)=7\cdot \Theta (1)$ somit haben wir die Aufwandsklasse $\Theta (fn))=\Theta (1)$

public int berechne(int n) { 
  int x = 0; 
  for (int i=1; i < n; i = 2*i) { 
    x = x + 1; 
  } 
  return x; 
}

Hier wächst die Laufvariable nicht linear an.Daher ist der Aufwand $f(n)=\Theta (1)+log_{2}n\cdot \Theta (1)+\Theta (1)$ und wir haben die Aufwandsklasse $\Theta (f(n))=\Theta (log~n)$ .

Doch gibt es eine allgemeine Methodik zum Bestimmen des Schleifenaufwands?

for (int i=1; i < n; i=2*i) { 
  x = x + 1;
}

Schritt 1: Wie entwickelt sich hier die Laufvariable? Der Startwert i ist 1 und die Veränderung in jedem Schritt ist $i=2\cdot i$ . Die Laufvariable entwickelt sich somit wie folgt:

Nach dem 1. Durchlauf $i=1\cdot 2=2^{1}$

Nach dem 2. Durchlauf $i=(1\cdot 2)\cdot 2=2^{2}$

Nach dem 3. Durchlauf $i=((1\cdot 2)\cdot 2)\cdot 2=2^{3}$

Nach dem k. Durchlauf $i=2^{k}$

Schritt 2: Nach wie vielen Durchläufen wird die Schleife abgebrochen?

Der Abbruch erfolgt, wenn $i\geq n$

: $i\geq n\ \ \ \ \ \ \ |i=2^{k}$

$\Leftrightarrow 2^{k}\geq n\ \ \ \ \ |log_{2}$

$\Leftrightarrow k\geq log_{2}n$

Somit erfolgt ein Abbruch nach $k=$ ⌈ $log_{2}n$ ⌉ Durchläufen.

public int berechne(int[] f1, int[] f2) { 
   int result = 0; 
   for (int i=0; i < f1.length; i++) { 
      for (int j=0; j < f2.length; j++) { 
         if (f1[i] == f2[j]) result++; 
      } 
   } 
   return result; 
}

Hier haben wir nun eine for Schleife mit mehreren Eingabevariablen. Die Problemgrößen sind $n=f1.length~und~m=f2.length$ .

public int berechne2(int[] f1, int[] f2){ 
   f2 = mergeSort(f2);
   int result = 0; 
   for (int i=0; i < f1.length; i++) {
      if (binarySearch(f2, f1[i])) result++; 
   } 
   return result;
}

Der Aufwand ist hier $f(n,m)=\Theta (m\cdot log~m)+\Theta (1)+n\cdot (\Theta (log~m)+O(1))+\Theta (1)$ . Somit ist die Aufwandsklasse $\Theta (f(n,m))=\Theta (m\cdot log~m+n\cdot log~m)$ .

In diesem Beispiel haben wir wieder mehreren Eingabevariablen. Diese sind die gleichen Problemgrößen $n=f1.length~und~m=f2.length$ .

public int berechne2(int[] f1, int[] f2){ 
   int result = 0; 
   for (int i=0; i < f1.length; i++) {
      for (int j=0; j < f2.length; j++) {
         if (f1[i] == f2[j]) result++; 
      }
   } 
   return result;
}

Der Aufwand ist hier wie folgt: $f(n,m)=\Theta (1)+n\cdot (m\cdot (\Theta (1)+O(1)))+\Theta (1)$ . Somit ist die Aufwandsklasse $\Theta (f(n,m))=\Theta (n\cdot m)$ .

Literatur

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.