Wie schnell ist ein Algorithmus?

Das lernst du

Die Schritte eines Programms zählen statt die Zeit zu stoppen
Erkennen, wie die Schrittzahl wächst, wenn die Daten doppelt so groß werden
Einen langsamen Algorithmus durch einen schnellen ersetzen

Schritte zählen statt Zeit stoppen

Wie schnell ein Programm ist, hängt auch vom Computer ab. Ein neuer Laptop ist schneller als ein alter. Informatiker zählen deshalb lieber die Schritte. Die Frage ist: Wie viele Schritte braucht ein Algorithmus, wenn die Daten größer werden?

In der Python-Lektion „Algorithmen“ hast du schon gesehen, dass die binäre Suche mit 20 Schritten auskommt, wo die lineare Suche eine Million braucht. Hier schauen wir genauer hin, wie die Schritte wachsen.

Eine Schleife: doppelt so viele Daten, doppelt so viele Schritte

Wer die größte Zahl einer Liste sucht, muss jede Zahl einmal anschauen. Bei doppelt so vielen Zahlen sind es doppelt so viele Schritte. Das nennt man linear:

def groesste(liste):
    schritte = 0
    beste = liste[0]
    for zahl in liste:
        schritte = schritte + 1
        if zahl > beste:
            beste = zahl
    return schritte


for n in [10, 20, 40, 80]:
    print(f"{n:3} Zahlen → {groesste(list(range(n))):3} Schritte")

Zwei verschachtelte Schleifen: viermal so viele Schritte

In einer Klasse soll jeder jedem einmal die Hand geben. Bei n Personen sind das n · (n − 1) / 2 Händedrücke. Verdoppelst du die Klasse, gibt es fast viermal so viele. Das nennt man quadratisch:

def haende(n):
    schritte = 0
    for a in range(n):
        for b in range(a + 1, n):
            schritte = schritte + 1
    return schritte


for n in [10, 20, 40, 80]:
    print(f"{n:3} Personen → {haende(n):5} Händedrücke")

Bei 80 Personen sind es schon 3160. Bei einer Million Datensätzen wären es 500 Milliarden Schritte – das dauert selbst für einen schnellen Computer viel zu lange.

Im Vergleich

Daten	linear	quadratisch	binäre Suche
10	10	45	4
1 000	1 000	499 500	10
1 000 000	1 000 000	≈ 500 Milliarden	20

Informatiker schreiben dafür O(n), O(n²) und O(log n). Das „O“ heißt: So ungefähr wächst die Schrittzahl, wenn n größer wird.

Kurz-Check

Wie viele Schritte zählt dieses Programm? Erst überlegen, dann tippen.

schritte = 0
for a in range(4):
    for b in range(4):
        schritte = schritte + 1
print(schritte)

Für die Aufgabe: Ein Blick in eine Menge (wert in gesehen) kostet nur einen Schritt, egal wie groß die Menge ist. Ein Blick in eine Liste muss dagegen im schlimmsten Fall jedes Element anschauen. Genau deshalb ist die schnelle Art so schnell.

Deine Aufgabe

Jetzt bist du dran

Finde heraus, ob in einer Liste ein Wert doppelt vorkommt – auf zwei Arten, und zähle die Vergleiche. doppelt_langsam(liste) vergleicht jedes Paar einmal (zwei verschachtelte Schleifen, die innere beginnt hinter der äußeren). doppelt_schnell(liste) merkt sich die schon gesehenen Werte in einer Menge und zählt jeden Blick in die Menge als einen Vergleich. Beide geben ein Paar zurück: (gefunden, vergleiche). Sobald ein doppelter Wert gefunden ist, hören beide sofort auf.

def doppelt_langsam(liste):
    vergleiche = 0
    return False, vergleiche


def doppelt_schnell(liste):
    vergleiche = 0
    gesehen = set()
    return False, vergleiche


zahlen = list(range(1000))
print(doppelt_langsam(zahlen))
print(doppelt_schnell(zahlen))

Denkanstoß
Gib (True, vergleiche) zurück, sobald zwei gleiche Werte gefunden sind – und (False, vergleiche) erst nach den Schleifen.
Welcher Befehl hilft?
Die innere Schleife beginnt hinter der äußeren: for j in range(i + 1, len(liste)) – dann zählst du jedes Paar genau einmal.
Pro Wert: vergleiche + 1, dann if wert in gesehen: … sonst gesehen.add(wert).

Lückencode – ergänze die ___

                        def doppelt_langsam(liste):
    vergleiche = 0
    for i in ___:
        for j in ___:
            vergleiche = ___
            if ___:
                return ___
    return False, vergleiche


def doppelt_schnell(liste):
    vergleiche = 0
    gesehen = set()
    for wert in ___:
        vergleiche = ___
        if ___:
            return ___
        gesehen.add(___)
    return False, vergleiche


zahlen = list(range(1000))
print(doppelt_langsam(zahlen))
print(doppelt_schnell(zahlen))

Ohne Hinweise gelöst gibt es einen ⭐ auf deiner Fortschrittsseite.

Lösung anzeigen

Versuch es erst selbst – aus Fehlern lernt man am meisten. Hier ist eine mögliche Lösung:

def doppelt_langsam(liste):
    vergleiche = 0
    for i in range(len(liste)):
        for j in range(i + 1, len(liste)):
            vergleiche = vergleiche + 1
            if liste[i] == liste[j]:
                return True, vergleiche
    return False, vergleiche


def doppelt_schnell(liste):
    vergleiche = 0
    gesehen = set()
    for wert in liste:
        vergleiche = vergleiche + 1
        if wert in gesehen:
            return True, vergleiche
        gesehen.add(wert)
    return False, vergleiche


zahlen = list(range(1000))
print(doppelt_langsam(zahlen))
print(doppelt_schnell(zahlen))