IT-Mathematik
Laufzeit & Big-O – Wie schnell ist ein Algorithmus?
Lernziele dieser Lektion
- Sie verstehen, warum die Laufzeit eines Programms von der Eingabegröße n abhängt
- Sie kennen die Big-O-Notation und können die Klassen O(1), O(log n), O(n), O(n·log n), O(n²), O(2^n) unterscheiden
- Sie wählen zwischen linearer und binärer Suche die passende Methode
- Sie schätzen Laufzeiten ab: Wie lange dauert ein Algorithmus bei n = 1.000.000?
- Sie lesen Komplexitäts-Angaben in Dokumentationen und entscheiden, ob ein Algorithmus für große Datenmengen geeignet ist
Warum zählt die Laufzeit?
Ein Algorithmus ist eine genau beschriebene Rechenvorschrift, die ein Problem löst. Zwei verschiedene Algorithmen können dasselbe Ergebnis liefern – aber mit völlig unterschiedlichem Zeitaufwand. Bei kleinen Datenmengen spielt das keine Rolle. Bei 1 Million Einträgen wird aus einem schlechten Algorithmus schnell eine Stunde Wartezeit.
Ein Alltagsbeispiel
Du suchst in einem Wörterbuch (sortiert, 1000 Seiten) das Wort „Zebra":
- Naiv (linear): Seite 1, Seite 2, Seite 3 … → im schlimmsten Fall 1000 Schritte
- Klug (binär): Mitte aufschlagen (Seite 500). „Zebra" weiter hinten → zwischen 500 und 1000 → Mitte (750). … → ~10 Schritte reichen!
Der binäre Ansatz ist in diesem Fall ca. 100-mal schneller. Genau das erfasst die Big-O-Notation.
Wie misst man Laufzeit?
Wir zählen nicht Sekunden (die hängen vom Computer ab), sondern Rechenschritte als Funktion der Eingabegröße n. Das ergibt eine Funktion T(n).
Definition: T(n)
T(n) = Anzahl der elementaren Operationen, die ein Algorithmus bei Eingabegröße n benötigt (im schlechtesten Fall).
Beispiel: Eine Liste mit n Einträgen Schritt für Schritt durchgehen → T(n) = n. Zwei verschachtelte Schleifen über n Elemente → T(n) = n².
Die Big-O-Notation
Für die Praxis interessiert uns nur das asymptotische Wachstum: Wie verhält sich T(n) für große n? Konstante Faktoren und kleinere Summanden werden weggelassen.
Vereinfachungsregel
Zwei Regeln:
- Nur der schnellstwachsende Summand zählt: T(n) = 3n² + 5n + 100 → O(n²)
- Konstante Vorfaktoren werden weggelassen: T(n) = 1000·n → O(n)
Wir schreiben T(n) ∈ O(f(n)) bzw. T(n) = O(f(n)) und lesen: „T wächst nicht schneller als f".
Dies ist nur ein kurzer Auszug. Die vollständige Lektion mit interaktiven Übungen und Lernfortschritts-Tracking gibt es nach Einlösung eines Einschreibeschlüssels.