Warum eine App bei vielen Daten lahmt
Die Zeitkomplexität sagt, wie stark die Zahl der Schritte eines Algorithmus wächst, wenn die Datenmenge wächst. Big O ist die kurze Schreibweise dafür, zum Beispiel O(n) oder O(n²).
Eine App kann mit 100 Einträgen flott laufen und mit einer Million stehen bleiben. Mit Big O siehst du das voraus, bevor du etwas baust.
Am Ende dieser Lektion
Notiz
Ich kann Algorithmen danach vergleichen, wie ihre Zahl der Schritte wächst.
Schlüsselwörter
| Begriff | Was er bedeutet | Beispiel |
|---|---|---|
| Schritt | eine einzelne Grundaktion, etwa ein Vergleich | |
| Zeitkomplexität | wie die Zahl der Schritte mit der Datenmenge wächst | |
| Big O | die Schreibweise für die Art des Wachstums | O(n) |
| Linear | doppelt so viele Daten, doppelt so viele Schritte | O(n) |
| Quadratisch | doppelt so viele Daten, viermal so viele Schritte | O(n²) |
| Logarithmisch | doppelt so viele Daten, nur ein Schritt mehr | O(log n) |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Warum wir Schritte zählen und keine Sekunden
Wie viele Sekunden ein Programm braucht, hängt vom Gerät ab: von deinem Handy, deinem Laptop oder einem Server. Dieselbe Zahl von Schritten ergibt auf jedem Gerät etwas anderes.
Die Zahl der Schritte dagegen ist auf jedem Gerät gleich und lässt sich genau zählen. Darum vergleichen wir Algorithmen damit.
Wie die Schritte mit n wachsen
| n | O(1) | O(log n) | O(n) | O(n²) |
|---|---|---|---|---|
| 10 | 1 | 4 | 10 | 100 |
| 100 | 1 | 7 | 100 | 10000 |
| 1000 | 1 | 10 | 1000 | eine Million |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Bevor du anfängst
Notiz
Drück oben in der Leiste auf Lab starten und warte, bis JupyterLab läuft. Die Schaltflächen Ausführen tippen ihren Befehl in das Terminal neben dem Lab. Jeder startet Python im Container jupyter.
n mal n für drei Größen ausrechnen
docker exec jupyter python3 -c "print([n * n for n in [10, 100, 1000]])"Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Die Vergleiche von Bubble Sort bei wachsendem n
Bubble Sort läuft mit einer Schleife in der Schleife. Der nächste Befehl schreibt ein Programm, das nur die Vergleiche zählt, bei 10, 20, 40 und 80 Werten. Es sortiert nichts. Der zweite Befehl startet es.
Das Zählprogramm in wachstum.py schreiben
docker exec jupyter sh -c "printf 'for n in [10, 20, 40, 80]:\n vergleiche = 0\n for runde in range(n - 1):\n for i in range(n - 1 - runde):\n vergleiche = vergleiche + 1\n print(n, vergleiche)\n' > wachstum.py"Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Die Vergleiche zählen lassen
docker exec jupyter python3 wachstum.pyHier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Was die Zahlen zeigen
| n | Vergleiche | Im Vergleich zur Zeile davor |
|---|---|---|
| 10 | 45 | Der Anfang |
| 20 | 190 | n doppelt, gut das Vierfache |
| 40 | 780 | n doppelt, gut das Vierfache |
| 80 | 3160 | n doppelt, gut das Vierfache |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Big O lässt Zahlen und kleine Teile weg
Bei einem großen n zählt nur der Teil, der am schnellsten wächst. Faktoren wie 3 und kleine Summanden wie 5 lässt man weg. Zwei Schleifen nacheinander addieren sich, eine Schleife in einer Schleife multipliziert.
So sagt O(n) nur: Die Schritte wachsen im gleichen Verhältnis wie n.
Beispiele für das Weglassen
| Schritte | Big O | Grund |
|---|---|---|
| 3n + 5 | O(n) | Der Faktor 3 und die 5 fallen weg |
| n² + n | O(n²) | n² wächst schneller als n |
| Zwei Schleifen nacheinander, je n | O(n) | n + n ist 2n |
| Schleife in Schleife, je n | O(n²) | n mal n |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Ein häufiger Fehler
Warnung
Viele glauben, O(n) heiße genau n Schritte. Es heißt nur: Die Schritte wachsen im gleichen Verhältnis wie n. Ein Algorithmus mit 3n Schritten und einer mit n Schritten sind beide O(n), sie unterscheiden sich nur im Faktor.
Die Schritte der binären Suche nachrechnen
docker exec jupyter python3 -c "print([n.bit_length() for n in [10, 100, 1000]])"Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Weiterführend: zwei Wege zur Summe
Die Summe der Zahlen von 1 bis n lässt sich mit einer Schleife berechnen, das sind n Schritte. Es geht auch mit der Formel n mal (n + 1) geteilt durch 2, in einem einzigen Schritt. Welche Klasse hat jeder Weg? Welchen würdest du bei einer Milliarde wählen?