Komplexität von Algorithmen

• Abschätzung des zeitlichen “Aufwands” eines Algorithmus in Abhängigkeit von der Anzahl n der Elemente
• “Aufwand”: Anzahl der “einfachen Operationen” (z.B. Wertzuweisung, Berechnung, Eingabe, Ausgabe, …)
• konstante Faktoren werden in der Regel ignoriert
• im Allgemeinen wird der “schlimmste Fall” betrachtet, d.h. der Fall mit dem größten Aufwand
  • worst case: schlimmster möglicher Fall
  • best case: bester möglicher Fall
  • average case: durchschnittlicher Fall

Komplexitätsklassen

• logarithmisch: $O(\log n)$
• linear - logarithmisch: $O(n\ast \log n)$
• linear: $O(x)$
• konstant: $O(1)$
• potentiell: $O(n^2),O(n^3),...$
• exponentiell: $O(x^n)(x>1)$

Beispiele:

Bsp. 1:

for (int i = 0; i < n; i++){
  System.out.println(i);
}

linear: $O(n)$

Bsp. 2:

for (int i = 0; i < n; i++){
  for (int j = 0; j < n; j++){
    k = j*i;
  }
}

potentiell: $O(n^2)$

Bsp. 3:

for (int i = 0; i < n; i++){
  for (int j = 0; j < 1000; j++){
    k = j*i;
  }
}

linear, da innere Schleife von n unabhängig ist: $O(n)$

Bsp. 4:

for (int i = 0; i < n; i++){
   x = i*i;
}
for (int j = 0; j < n; j++){
   k = j*j;  
}

linear, da schleifen nicht ineinander geschachtelt: $O(n)$

Bsp. 5:

for (int i = 0; i < n*n; i++){
  for (int j = n/2; j < n; j++){
    k = j*i;  
  }
}

potentiell: $O(n^3)$

Bsp. 6:

for (int i = 0; i <= n; i++){  
  for (int j = 0; j < i; j++){
 
  }
}

potentiell Durchläufe $\frac{n^2+n}{2}$ konstante Faktoren entfernen und nur den höhsten Faktor aufschreiben: $O(n^2)$

Bsp. 7:

linear - logarithmisch: $O(n\ast \log n)$ Kommt vor bei: Quicksort, Binärsuche, Suche in Binärbaumen