Algorithmen und Laufzeit

Lernziele

Probleme in klare Schritte zerlegen und Aufwand vergleichen. Nach dieser Lektion kannst du das Konzept erklären, ein kleines Beispiel umsetzen und typische Grenzen benennen.

Erklärung

Ein Algorithmus ist eine endliche, präzise Folge von Schritten. Korrektheit fragt, ob das Ergebnis stimmt; Laufzeitanalyse fragt, wie der Aufwand mit der Eingabegröße wächst. Lineare Suche prüft höchstens n Elemente. Binäre Suche halbiert einen sortierten Suchraum und braucht ungefähr log₂(n) Schritte.

Schrittweises Beispiel

Bei 16 sortierten Einträgen reichen vier Halbierungen: 16 → 8 → 4 → 2 → 1. Binäre Suche ist nur korrekt, wenn die Daten sortiert sind.

names = ["Ada", "Grace", "Linus"]
target = "Grace"
for index, name in enumerate(names):
    if name == target:
        print(index)

Zusammenfassung

Formuliere Vorbedingungen und Nachbedingungen. Big O beschreibt Wachstum, nicht eine genaue Sekundenangabe.