Big-O-Wachstum: was jede Komplexitätsklasse wirklich kostet
Ihre Daten
Zwei Algorithmen im direkten Vergleich
Die Konstante ist alles, was die Notation wegwirft: Allokationen, Cache-Misses, die Arbeit innerhalb jedes Schritts. Geben Sie einem Algorithmus eine schwerere Konstante und sehen Sie, ab wo sie nicht mehr zählt.
Diese Seite liest Ihre Schleife nicht. Eine Komplexität aus dem Quelltext zu raten wäre eine Vermutung im Kostüm einer Messung: Eine Schleife kann früh abbrechen, ein einziger Aufruf darin kann die eigentlichen Kosten verstecken, und Rekursion liest sich selten als das, was sie tut. Sie wählen die Klasse; was die Seite daraus berechnet, ist exakt.
Ergebnisse
| Wo der eine den anderen überholt, in Elementen | — |
| Operationen von jedem, bei der Größe oben | — |
Mit den Zahlen, mit denen diese Seite startet, liegt der Kreuzungspunkt bei 439 Elementen. Wer bei einer Liste von zweihundert zur besseren Klasse greift, hat das Programm langsamer und den Code schwerer gemacht, und die Notation hat nicht gewarnt — denn sie spricht davon, was am Ende passiert, nicht davon, was Ihnen passiert.
Jede Klasse bei dieser Größe
| Klasse | Operationen | Zeit | Multipliziert mit, wenn die Eingabe sich verdoppelt |
|---|
Die letzte Spalte lohnt das Hinstarren, denn sie ist die Spalte, die niemand im Kopf hat. Lineare Arbeit verdoppelt sich. Quadratische vervierfacht sich. Exponentielle wird quadriert: bei bereits tausend Elementen multipliziert das Verdoppeln der Eingabe die Kosten mit zwei hoch tausend, einer Zahl mit dreihundertzwei Stellen.
Fakultät ist auf eine Weise schlimmer, die mit Verdoppeln nichts zu tun hat. Ein einziges zusätzliches Element multipliziert die Kosten mit der neuen Anzahl: das einundzwanzigste Element kostet einundzwanzigmal das ganze Zwanzig-Element-Problem. Deshalb sind ein exakter Handlungsreisender über zwanzig Städte 2,4 Millionen Millionen Millionen Schritte, also siebenundsiebzig Jahre bei einer Milliarde pro Sekunde, während dieselben zwanzig Städte unter zwei hoch n in einer Tausendstelsekunde fertig sind.
Das erklärt auch, warum der Abstand zwischen Klassen bei kleinen Größen langweilig und bei großen brutal ist. Bei zehn Elementen liegen n log n und n Quadrat um das Dreifache auseinander, was kein Nutzer bemerkt. Bei tausend Elementen um das Hundertfache, bei einer Million um das Fünfzigtausendfache. Dieselben zwei Algorithmen, derselbe Code, nichts geändert außer der Eingabe.
Ehrlich gelesen ist eine Komplexitätsklasse also ein Versprechen über die Form der Kurve, nicht über Geschwindigkeit. Sie sagt, wie die Kosten reagieren, wenn die Eingabe wächst, und überhaupt nichts darüber, ob es heute, auf Ihrer Maschine, bei Ihrer tatsächlichen Größe schnell ist.
Bedeutet eine bessere Komplexitätsklasse ein schnelleres Programm?
Bei Ihrer Größe nicht unbedingt. Die Klasse beschreibt, wie die Kosten auf wachsende Eingaben reagieren; über die Arbeit innerhalb jedes Schritts sagt sie nichts, und genau diese Arbeit wirft die Notation weg.
Mit den Zahlen, mit denen diese Seite startet, schlägt der quadratische Algorithmus mit leichter Konstante den n-log-n-Algorithmus mit Konstante fünfzig bei jeder Eingabe unter 439 Elementen. Darüber zieht die bessere Klasse davon und gibt die Führung nie wieder ab.
Warum liest diese Seite meinen Code nicht?
Weil eine Komplexität aus dem Quelltext zu raten eine Vermutung im Kostüm einer Messung ist. Eine Schleife kann früh abbrechen, ein Aufruf darin kann die eigentlichen Kosten verstecken, und Rekursion liest sich selten als das, was sie tut.
Die Klasse ist hier also Ihre Eingabe, nicht die Meinung der Seite. Alles daraus Berechnete ist exakte Arithmetik, und nichts auf dieser Seite tut so, als wüsste es, was Ihre Schleife tut.
Was passiert wirklich, wenn die Eingabe sich verdoppelt?
Lineare Arbeit verdoppelt sich und quadratische vervierfacht sich — das haben die meisten im Kopf. Exponentielle wird quadriert, und das hat fast niemand im Kopf: bei tausend Elementen multipliziert das Verdoppeln der Eingabe die Kosten mit zwei hoch tausend.
Fakultät funktioniert nicht einmal so. Ein einziges zusätzliches Element multipliziert die Kosten mit der neuen Anzahl: das einundzwanzigste Element kostet einundzwanzigmal das ganze Zwanzig-Element-Problem.
| Klasse | Multipliziert mit beim Verdoppeln der Eingabe, bei tausend Elementen |
|---|---|
| O(n) | 2 |
| O(n log n) | 2,2 |
| O(n²) | 4 |
| O(n³) | 8 |
| O(2ⁿ) | 1,07 x 10^301 |
Warum ist ein exakter Handlungsreisender bei zwanzig Städten unmöglich?
Weil zwanzig Fakultät 2,4 Millionen Millionen Millionen Schritte sind, was bei einer Milliarde Operationen pro Sekunde siebenundsiebzig Jahre ergibt. Dieselben zwanzig Elemente unter zwei hoch n brauchen etwa eine Tausendstelsekunde.
Das ist der praktische Unterschied zwischen exponentiell und faktoriell, und deshalb lohnt es, die beiden zu trennen, statt beide unter unmöglich abzulegen.
Reaktionen
0
0 Kommentare
Sei der erste der kommentiert