Zeitkomplexität: Schritte zählen
Kurz gesagt: Die Zeitkomplexität sagt, wie die Zahl der Grundoperationen mit der Größe der Eingabe wächst: Eine verschachtelte Schleife macht n(n − 1) / 2 Schritte, ein Durchlauf mit einem Set macht n.
Problem
Der Bericht, der nie fertig wird
Jeden Monat lässt der Online-Shop einen Verkaufsbericht laufen. Eine seiner Prüfungen sucht doppelte Zahlungen: dieselbe Zahlung zweimal abgebucht, weil jemand den Knopf noch einmal gedrückt hat. Die Methode vergleicht jede Zahlung mit jeder Zahlung danach:
static int doublePayments(int[] ids) { int found = 0; for (int i = 0; i < ids.length; i++) { for (int j = i + 1; j < ids.length; j++) { if (ids[i] == ids[j]) { found++; } } } return found;}int[] ids = {100231, 100232, 100233, 100232, 100234};System.out.println("Doppelzahlungen: " + doublePayments(ids));Doppelzahlungen: 1Vor einem Jahr gab es 1.000 Bestellungen im Monat, und der Bericht war in 2 Sekunden fertig. Heute sind es 100.000. Der Bericht startet am Abend und läuft am Morgen noch. Niemand hat den Code angefasst. Die Daten sind 100-mal größer, und die Zeit ist nicht 100-mal länger, sondern viel länger.
Warum? Und wie könntest du es im Voraus wissen, ohne die ganze Nacht zu warten?
Die Idee
Sekunden lügen, Schritte nicht
Wie viele Sekunden ein Programm braucht, hängt von vielen Dingen außerhalb des Programms ab:
- die Maschine: Laptop und Server liefern unterschiedliche Zahlen;
- die Last: Derselbe Bericht ist langsamer, solange der Server auch Kunden bedient;
- die Sprache: Dieselbe Berechnung ist in Python um ein Mehrfaches langsamer als in Java oder C#.
Also messen wir etwas anderes: wie oft das Programm seine Grundoperation ausführt. Hier ist das ein Vergleich zweier Zahlen. Ihre Anzahl hängt weder von der Maschine noch von der Sprache ab, nur vom Algorithmus und von der Eingabe. Man nennt sie die Zahl der Operationen (oder die Zahl der Schritte).
Die Zahl der Operationen verrät dir nicht die Sekunden. Sie verrät dir etwas Nützlicheres: wie viel mehr Arbeit kommt, wenn die Daten wachsen.
Sieh es dir an
Die Schritte zählen
Du stellst einen Zähler neben den Vergleich. Jeder Vergleich ist ein Schritt:
static long steps = 0;
static int doublePayments(int[] ids) { int found = 0; for (int i = 0; i < ids.length; i++) { for (int j = i + 1; j < ids.length; j++) { steps++; if (ids[i] == ids[j]) { found++; } } } return found;}Der Bericht läuft mit 10, 1.000 und 2.000 Zahlungen mit unterschiedlichen Nummern:
for (int n : new int[] {10, 1000, 2000}) { int[] ids = new int[n]; for (int k = 0; k < n; k++) { ids[k] = 100000 + k; } steps = 0; doublePayments(ids); System.out.println("n = " + n + ": " + steps + " Schritte");}n = 10: 45 Schritten = 1000: 499500 Schritten = 2000: 1999000 SchritteDie erste Zahlung wird mit n − 1 anderen verglichen, die zweite mit n − 2, und so weiter bis zur letzten, für die niemand mehr übrig ist. Die Summe ist
n(n − 1) / 2
Bei 1.000 Zahlungen sind das 499.500 Schritte. Bei 100.000 sind es 4.999.950.000: 10.010-mal mehr bei 100-mal mehr Daten. Gingen die zwei Sekunden fast ganz für die Vergleiche drauf, sind es jetzt mehr als fünfeinhalb Stunden. Die Antwort stand vor einem Jahr schon im Code: Du musstest nur zählen.
Sieh es dir an
Warum fast ×4
static long steps = 0;
static int doublePayments(int[] ids) { int found = 0; for (int i = 0; i < ids.length; i++) { for (int j = i + 1; j < ids.length; j++) { steps++; if (ids[i] == ids[j]) { found++; } } } return found;}static long steps = 0;
static int doublePayments(int[] ids) { int found = 0; for (int i = 0; i < ids.length; i++) { for (int j = i + 1; j < ids.length; j++) { steps++; if (ids[i] == ids[j]) { found++; } } } return found;}static long steps = 0;
static int doublePayments(int[] ids) { Set<Integer> seen = new HashSet<>(); int found = 0; for (int id : ids) { steps++; if (!seen.add(id)) { found++; } } return found;}Schritt für Schritt, in Worten
- Vier Zahlungen. Die äußere Schleife nimmt die erste, i = 0: Sie wird mit jeder Zahlung danach verglichen.
- j geht die Zahlungen nach i durch. Jeder Vergleich ist ein Schritt, und die Zelle des Paars leuchtet auf: steps = 1, 2, 3.
- i rückt weiter, und j beginnt wieder bei i + 1. Die Paare sind 3 + 2 + 1 = 6: ein Dreieck.
- Doppelt so viele Zahlungen: 8. Die Schritte sind nicht 12, sondern 28.
- 28 = 6 alte Paare + 6 Paare unter den neuen + 16 Paare aus einer neuen mit einer alten. Fast ×4: Bei 1 000 → 2 000 Zahlungen sind es 499 500 → 1 999 000 Schritte.
- Die Korrektur geht die Zahlungen einmal durch und merkt sie sich in seen: 8 Zahlungen, 8 Schritte. Doppelt so viele Zahlungen heißt hier doppelt so viele Schritte.
Verdoppeln heißt nicht nur „noch einmal so viele Zahlungen“. Die alten 6 Paare bleiben. 6 Paare entstehen unter den neuen Zahlungen. Und 16 weitere: jede der 4 neuen mit jeder der 4 alten. Zusammen 28. Der Teil „neu mit alt“ ist ein Quadrat, und es wächst am schnellsten. Deshalb ergibt das Verdoppeln bei großem n fast genau ×4.
Genauer, für Neugierige
Die Rechnung für jedes n: Bei 2n Zahlungen sind die Paare 2n(2n − 1) / 2 = 4 · n(n − 1) / 2 + n. Das sind viermal die alten Paare und n mehr. Mit n = 4 ist das 4 · 6 + 4 = 28, und mit n = 1.000 ist es 4 · 499.500 + 1.000 = 1.999.000. Das zusätzliche n ist klein neben dem Rest, und je größer n ist, desto kleiner wird es.
Probier es aus
Sag die Ausgabe voraus
Zwei verschachtelte Schleifen. Die erste geht über 4 Lager und für jedes über 3 Lieferzeiten. Die zweite geht über jedes Paar der 4 Lager. Was gibt das Programm aus?
int full = 0;for (int i = 0; i < 4; i++) { for (int j = 0; j < 3; j++) { full++; }}int pairs = 0;for (int i = 0; i < 4; i++) { for (int j = i + 1; j < 4; j++) { pairs++; }}System.out.println(full + " " + pairs);Die erste ist voll: 4 × 3 = 12. In der zweiten beginnt die innere Schleife bei i + 1: 3 + 2 + 1 = 6, das ist 4 · 3 / 2.
Probier es aus
Ergänze
Der Bericht muss jedes Paar genau einmal vergleichen und nie eine Zahlung mit sich selbst. Wo beginnt die innere Schleife?
static int doublePayments(int[] ids) {
int found = 0;
for (int i = 0; i < ids.length; i++) {
for (int j = ; j < ids.length; j++) {
if (ids[i] == ids[j]) {
found++;
}
}
}
return found;
}Bei i + 1. Ab 0 würde jedes Paar zweimal verglichen (i mit j und j mit i), und jede Zahlung auch mit sich selbst, also käme jede Zahlung als „doppelt“ heraus.
Sieh es dir an
Die Korrektur: ein Durchlauf
Man muss nicht jede Zahlung mit jeder anderen vergleichen. Es genügt, sich die Nummern zu merken, die man schon gesehen hat. Ein Set hält diese Nummern und sagt dir, ob eine Nummer darin ist, ohne sie eine nach der anderen durchzugehen.
static long steps = 0;
static int doublePayments(int[] ids) { Set<Integer> seen = new HashSet<>(); int found = 0; for (int id : ids) { steps++; if (!seen.add(id)) { found++; } } return found;}seen.add(id) gibt false zurück, wenn die Nummer schon im Set ist: Dann ist die Zahlung doppelt.for (int n : new int[] {10, 1000, 2000}) { int[] ids = new int[n]; for (int k = 0; k < n; k++) { ids[k] = 100000 + k; } steps = 0; doublePayments(ids); System.out.println("n = " + n + ": " + steps + " Schritte");}n = 10: 10 Schritten = 1000: 1000 Schritten = 2000: 2000 SchritteDie Schritte sind so viele wie die Zahlungen. Doppelt so viele Zahlungen heißt doppelt so viele Schritte. Lass die beiden Berichte nebeneinander laufen:
- Jedes Paar von Bestellungen
O(n²) - Der Bericht mit einer Menge (Set)
O(n)
| Algorithmus | n = 10 | n = 1.000 | n = 2.000 | n = 4.000 | n = 100.000 |
|---|---|---|---|---|---|
| Jedes Paar von Bestellungen | 45 | 499.500 | 1.999.000 | 7.998.000 | ≈ 4.998.750.000 |
| Der Bericht mit einer Menge (Set) | 10 | 1.000 | 2.000 | 4.000 | 100.000 |
Genauer, für Neugierige
Welche Operation ist die Grundoperation? Die, die sich am häufigsten wiederholt und von der die Zeit abhängt. Im langsamen Bericht ist das der Vergleich in der inneren Schleife. Das Erhöhen von i und j und die Prüfung, ob die Schleife zu Ende ist, wiederholen sich auch, aber genauso oft wie die Vergleiche, nicht öfter. Ihre Anzahl ändert das Bild also nicht und wird nicht gesondert gezählt.
Ist die Prüfung im Set ein Schritt? Nicht ganz: Hinter dem Set steckt eine Hashtabelle, die den Hash der Nummer berechnet und in einen Bucket schaut. Im Durchschnitt ist das immer dieselbe kleine Menge Arbeit, egal wie viele Nummern darin liegen. Wie das geht, siehst du im Modul „Datenstrukturen“. Hier zählen wir es als einen Schritt, genau wie Bench.
Sekunden in den verschiedenen Sprachen. Die Zahl der Schritte ist gleich, die Zeit nicht. Java übersetzt die heiße Schleife zur Laufzeit in Maschinencode (JIT), deshalb sind die ersten tausend Schritte langsamer als die späteren. HashSet<Integer> hält Integer-Objekte, nicht int, und jede Zahl wird verpackt (Boxing). Das kostet pro Schritt etwas mehr, ändert aber nicht ihre Anzahl.
Übung
Verkäufe nach Produkt
Löse die Aufgabe in deinem Editor.
Wie viele Schritte. Der Verkaufsbericht zählt, wie oft jedes der 50 Produkte bestellt wurde. Eine Bestellung ist die Nummer des Produkts (von 0 bis 49):
static int[] salesByProduct(int[] orders, int products) { int[] sales = new int[products]; for (int p = 0; p < products; p++) { for (int product : orders) { if (product == p) { sales[p]++; } } } return sales;}Füge vor dem Vergleich einen Zähler steps hinzu. Lass die Methode mit 1.000 und mit 2.000 Bestellungen laufen, wobei das Produkt der Bestellung k gleich k % 50 ist, und gib die Schritte aus:
n = 1000: 50000 Schritten = 2000: 100000 SchritteDie Schleife ist verschachtelt, und trotzdem verdoppeln sich die Schritte nur. Warum?
Weitere Aufgaben
- Ein Durchlauf. Schreibe den Verkaufsbericht mit einem Durchlauf über die Bestellungen:
sales[product]wächst für jede Bestellung um eins. Wie viele Schritte sind es bei 1.000 Bestellungen? - Der Bericht des Jahres. Wie viele Schritte macht der langsame Bericht über doppelte Zahlungen für ein ganzes Jahr mit 100.000 Zahlungen im Monat? Rechne es mit n(n − 1) / 2 aus, ohne es laufen zu lassen.
- Dein Code. Suche in deinem eigenen Code eine verschachtelte Schleife und zähle ihre Schritte für zwei Eingabegrößen. Was passiert, wenn sich die Eingabe verdoppelt?
Test