prev up next

Previous: O-Notation Up: O-Notation Next: Analyse von while-Schleifen

Analyse von for-Schleifen

Beispiel: Minimumsuche in einem Array der Länge $ n $

min = a[0];
for (i = 1; i < n; i++){
       if(a[i] < min) min = a[i];
}
Laufzeit $O(n)$ für best case
  worst case
  average case.
Beispiele:

s = 0;                                int treffer=0;
for (i = 0; i < k; i++) {             for (i = 0, i < k-1; i++) {
   for (j = 0; j < k; j++) {             for (j = i+1; j < k; j++) {
      s = s + brett[i][j];                  if (a[i] == a[j]) treffer++;
   }                                     }
}                                     }

$k^2$ Schritte für $k^2$ Daten $\qquad \qquad \qquad \qquad $ $(k \cdot (k-1))/2$ Schritte für $k$ Daten
$\Rightarrow O(n)-$Algorithmus   $\Rightarrow O(n^2 )-$Algorithmus


prev up next
Previous: O-Notation Up: O-Notation Next: Analyse von while-Schleifen