Warum ein Verfahren bei mehr Daten plötzlich scheitert
Die Komplexität eines Algorithmus sagt, wie stark die Zahl seiner Schritte wächst, wenn die Datenmenge wächst. Mit ihr sehen Sie vorher, ob ein Verfahren auch bei einer großen Datenmenge noch funktioniert.
Eine Hochschulbibliothek prüft, ob ein Buch doppelt im Katalog steht. Bei 200 Büchern geht das sofort. Bei 200.000 Büchern läuft dasselbe Programm stundenlang. Der Grund liegt nicht im Rechner, sondern in der Zahl der Schritte.
Am Ende dieser Lektion
Notiz
Ich kann die Schritte eines Algorithmus zählen und sagen, wie die Zahl mit der Eingabegröße wächst.
Schlüsselwörter
| Begriff | Was er bedeutet | Beispiel |
|---|---|---|
| Algorithmus | eine genaue Folge von Schritten, die ein Problem löst | |
| Schritt | eine einfache Anweisung, die einmal ausgeführt wird | summe = summe + 1 |
| Eingabegröße | wie viele Daten ein Algorithmus bekommt, kurz n | n = 1000 |
| Komplexität | wie die Zahl der Schritte mit n wächst | |
| Wachstumsklasse | eine Gruppe von Algorithmen mit gleichem Wachstum | linear |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Ein Schritt ist eine einfache Anweisung
Ein Algorithmus ist eine genaue Folge von Anweisungen. Wir zählen seine Schritte: eine Addition, ein Vergleich, eine Zuweisung.
Wir fragen nicht, wie lange ein Schritt dauert. Wir fragen nur, wie viele es sind. Diese Zahl hängt von der Eingabegröße n ab und ist auf jedem Rechner gleich.
Eine Schleife mit Zähler
# Wie viele Schritte macht diese Schleife?
preise = [4, 9, 2, 7, 5]
summe = 0
schritte = 0
for preis in preise:
summe = summe + preis
schritte = schritte + 1 # ein Durchlauf ist ein Schritt
print("Summe:", summe, "Schritte:", schritte)
# Aendern Sie die Liste auf zehn Preise und fuehren Sie erneut aus.
Beispiele: wie viele Schritte bei welchem n
| Algorithmus | n = 5 | n = 10 | n = 1000 |
|---|---|---|---|
| Den ersten Preis lesen | 1 | 1 | 1 |
| Alle Preise addieren | 5 | 10 | 1000 |
| Jeden Preis mit jedem anderen vergleichen (Paare) | 10 | 45 | 499.500 |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Vier Wachstumsklassen reichen für den Anfang
Wir ordnen Algorithmen nach ihrem Wachstum. Konstant heißt: immer gleich viele Schritte. Linear heißt: doppelt so viele Daten, doppelt so viele Schritte.
Quadratisch heißt: doppelt so viele Daten, viermal so viele Schritte. Logarithmisch heißt: doppelt so viele Daten, nur ein Schritt mehr. Das ist das beste Wachstum, das man bei Daten erwarten kann.
So wächst jede Klasse
| Klasse | Beispiel | n = 10 | n = 1000 | n verdoppelt sich |
|---|---|---|---|---|
| konstant | Das erste Element lesen | 1 | 1 | bleibt gleich |
| logarithmisch | Binäre Suche, schlimmster Fall | 4 | 10 | ein Schritt mehr |
| linear | Alle Elemente einmal lesen | 10 | 1000 | doppelt so viele |
| quadratisch | Jedes Element mit jedem vergleichen | 100 | 1.000.000 | viermal so viele |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Die Paare zählen und die Liste verdoppeln
# Jede Lieferung mit jeder anderen vergleichen.
mengen = [4, 8, 15, 16, 23]
vergleiche = 0
for i in range(len(mengen)):
for j in range(i + 1, len(mengen)):
vergleiche = vergleiche + 1
print("Elemente:", len(mengen), "Vergleiche:", vergleiche)
# Machen Sie die Liste doppelt so lang. Wie viele Vergleiche sind es dann?
Im Lab: die Größenordnungen nachrechnen
Im Lab prüfen Sie die Zahlen der Tabelle am Terminal. Der erste Befehl zählt, wie viele Binärstellen die Zahl 1000 und die Zahl 1.000.000 haben. Das ist genau die Zahl der Schritte einer binären Suche im schlimmsten Fall.
Der zweite erzeugt 1000 Zeilen und zählt sie. Das ist ein linearer Vorgang: ein Schritt je Zeile.
Stellen von 1000 und 1.000.000
python3 -c "print((1000).bit_length(), (1000000).bit_length())"Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Tausend Zeilen zählen
seq 1 1000 | wc -lHier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Warum wir Schritte zählen und nicht Sekunden
Der Befehl time misst, wie lange ein Befehl dauert. Die Zahlen unterscheiden sich aber von Rechner zu Rechner und sogar von Lauf zu Lauf.
Die Zahl der Schritte ist dagegen immer gleich. Deshalb vergleichen wir Algorithmen über ihre Schritte. Der nächste Befehl zeigt, dass time drei Zeilen mit Zeiten anhängt.
Die Zeit eines Befehls ansehen
time seq 1 100000 | wc -lHier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Ein häufiger Fehler
Warnung
Viele denken, ein schnellerer Rechner mache einen Algorithmus besser. Er verkürzt nur jeden Schritt. Die Klasse bleibt: Ein quadratischer Algorithmus braucht bei doppelter Datenmenge weiter viermal so viele Schritte.
Weiterführend
Schreiben Sie pruefe_paare so um, dass die Schleife beim ersten gleichen Paar abbricht. Wie viele Vergleiche braucht die Liste [4, 8, 4] jetzt?
Der schlimmste Fall bleibt quadratisch. Überlegen Sie, bei welcher Liste er eintritt.