Notationen
| Notation | Definition | Zweck | Beispiel |
| O-Notation (Big O) | Die O-Notation beschreibt das schlechteste Szenario der Laufzeit eines Algorithmus | Sie gibt an, wie die Laufzeit eines Algorithmus im schlimmsten Fall wächst, wenn die Eingabegröße gegen unendlich geht. | Wenn ein Algorithmus eine Laufzeit von O(n²) hat, bedeutet das, dass die Laufzeit im schlimmsten Fall quadratisch zur Eingabegröße n wächst. |
| Small-o-Notation (small o) | Die Small-o-Notation beschreibt eine obere Schranke für die Laufzeit eines Algorithmus, die jedoch nicht notwendigerweise die schlechteste Laufzeit ist. Sie gibt an, dass die Laufzeit eines Algorithmus asymptotisch kleiner ist als eine bestimmte Funktion. | Sie wird verwendet, um zu zeigen, dass die Laufzeit eines Algorithmus schneller wächst als eine bestimmte Funktion, aber langsamer als eine andere. | Wenn ein Algorithmus eine Laufzeit von o(n²) hat, bedeutet das, dass die Laufzeit asymptotisch kleiner ist als n², aber nicht notwendigerweise im schlimmsten Fall. |
| Omega-Notation (Big Ω) | Die Omega-Notation beschreibt das beste Szenario der Laufzeit eines Algorithmus. | Sie gibt an, wie die Laufzeit eines Algorithmus im besten Fall wächst, wenn die Eingabegröße gegen unendlich geht. | Wenn ein Algorithmus eine Laufzeit von Ω(n) hat, bedeutet das, dass die Laufzeit im besten Fall linear zur Eingabegröße n wächst. |
| Kleine Omega-Notation (kleines ω) | Die kleine Omega-Notation beschreibt eine untere Schranke für die Laufzeit eines Algorithmus, die jedoch nicht notwendigerweise die beste Laufzeit ist. Sie gibt an, dass die Laufzeit eines Algorithmus asymptotisch größer ist als eine bestimmte Funktion. | Sie wird verwendet, um zu zeigen, dass die Laufzeit eines Algorithmus langsamer wächst als eine bestimmte Funktion, aber schneller als eine andere. | Wenn ein Algorithmus eine Laufzeit von ω(n) hat, bedeutet das, dass die Laufzeit asymptotisch größer ist als n, aber nicht notwendigerweise im besten Fall. |
| Theta-Notation (Θ) | Die Theta-Notation beschreibt sowohl die obere als auch die untere Schranke der Laufzeit eines Algorithmus. Sie gibt an, dass die Laufzeit eines Algorithmus asymptotisch zwischen zwei Funktionen liegt. | Sie wird verwendet, um die genaue Wachstumsrate der Laufzeit eines Algorithmus zu beschreiben, indem sie sowohl das beste als auch das schlechteste Szenario berücksichtigt. | Wenn ein Algorithmus eine Laufzeit von Θ(n²) hat, bedeutet das, dass die Laufzeit asymptotisch sowohl durch n² nach oben als auch nach unten beschränkt ist. Exakte Wachstumsrate (sowohl obere als auch untere Schranke) |
O-Notation (Big O)
- Zweck: Beschreibt das schlechteste Szenario der Laufzeit eines Algorithmus. Sie gibt an, wie die Laufzeit im schlimmsten Fall wächst, wenn die Eingabegröße gegen unendlich geht.
Omega-Notation (Big Ω)
- Zweck: Beschreibt das beste Szenario der Laufzeit eines Algorithmus. Sie gibt an, wie die Laufzeit im besten Fall wächst, wenn die Eingabegröße gegen unendlich geht.
Small-o-Notation (kleines o)
- Zweck: Beschreibt eine obere Schranke für die Laufzeit eines Algorithmus, die jedoch nicht notwendigerweise die schlechteste Laufzeit ist. Sie zeigt, dass die Laufzeit asymptotisch kleiner ist als eine bestimmte Funktion.
Theta-Notation (Θ)
- Zweck: Beschreibt sowohl die obere als auch die untere Schranke der Laufzeit eines Algorithmus. Sie gibt die genaue Wachstumsrate der Laufzeit an, indem sie sowohl das beste als auch das schlechteste Szenario berücksichtigt.
Kleine Omega-Notation (kleines ω)
- Zweck: Beschreibt eine untere Schranke für die Laufzeit eines Algorithmus, die jedoch nicht notwendigerweise die beste Laufzeit ist. Sie zeigt, dass die Laufzeit asymptotisch größer ist als eine bestimmte Funktion.