Dies ist der dritte Artikel in einer siebenteiligen Reihe über Algorithmen und Berechnungen, in der untersucht wird, wie wir einfache Binärzahlen verwenden, um unsere Welt mit Energie zu versorgen. Der erste Artikel Wie Algorithmen die Welt steuern, in der wir leben , kann gefunden werden hier .
Wenn Sie eine Visualisierung von sehen verschiedene Sortieralgorithmen Wenn Sie an einem Datensatz arbeiten, wird sehr schnell klar, dass einige viel besser sind als andere. Wo ein Algorithmus verwendet wird Sekunden bis zum Ende wird ein anderer nehmen Minuten auch bei kleinen Datenmengen. Glücklicherweise müssen wir den Algorithmus nicht bei der Arbeit sehen, um zu wissen, ob der Algorithmus die Aufgabe schnell erledigen kann oder ob er unter dem Gewicht seiner Eingabe zusammenbrechen wird. Das ist was Big O-Notation ist für, und es kann uns auf einen Blick sagen, ob die Zeitkomplexität von einem Algorithmus bedeutet, dass wir ihn in wenigen bekommen werden Stunden oder Milliarden von Jahren .
Was ist Zeitkomplexität?
formeller ausgedrückt zeitliche Komplexität ist die Messung, wie lange ein Algorithmus benötigt, um zu produzieren ein Ergebnis , bezogen auf die Größe von sein Eingang . Praktisch es ist das Wachstumsrate in der Anzahl der Operationen erforderlich, um ein Ergebnis für zu erstellen jede zusätzliche Eingabeeinheit .
In der erster Artikel in dieser Serie habe ich eine einfache beschrieben Summationsalgorithmus . Zur Berechnung der Summe von alle Zahlen dazwischen die Zahlen p und q , ich habe eine andere Variable deklariert, r und setzen Sie es auf Null . Ich habe dann hinzugefügt p zu r , dann habe ich hinzugefügt p + 1 zu r dann p + 2 und so weiter, bis ich endlich hinzugefügt habe q selbst zu r an diesem Punkt habe ich angehalten und das Ergebnis zurückgegeben r , der die hielt Summe .
Wie viele Operationen sind erforderlich, ohne die endgültige Eingabegröße zu kennen, wenn nur die abstrakten Variablen verwendet werden? p und q ? Was wir tatsächlich tun, ist a Schleife wobei jede Iteration zunimmt p genau 1 und fügt es hinzu r . So sieht unser Algorithmus tatsächlich aus, wenn er etwas formeller dargestellt wird :
1. lassen r = 0
2. während p ist <= zu q
3. r = p + r
4. p = p + 1
5. Rückkehr r
Wenn in dem, was wir nennen, so angelegt ist Pseudocode, Es wird viel einfacher zu sehen, wie viele Operationen dies dauern wird. Gehen Sie die Schritte Nummer für Nummer durch und zählen Sie die Operationen. Die erste ist eine Anweisung, also eine einzelne Operation. Die zweite Zeile ist jedoch anders. Schleifenso wiederholen, bis die Bedingung erfüllt ist, in diesem Fall einmal p ist größer als q. Wir wissen dann, dass wir einschließen q und p in der Summe , also die Anzahl der Iterationen durch diese Schleife ist gleich q - p - 1, welches ist das Eingabegröße für unseren Algorithmus.
Aber das ist nur die Häufigkeit, mit der wir die Schleife durchlaufen. Wir müssen auch die darin enthaltenen Operationen zählen, die wir hinzufügen. p und r und zuweisen das Ergebnis zu r und dann fügen wir hinzu p und 1 und ordnen Sie dann das Ergebnis zu S. Also treten wir auf zwei Operationen für jeden Iteration und es gibt q - p - 1 Iterationen. Jetzt müssen wir nur noch multiplizieren. 2 Operationen und q - p - 1 Iterationen zu bekommen 2 * q - p - 1 Operationen für die gesamte Schleife. Fügen Sie die Operationen bei 1. und 5. hinzu, wodurch wir eine endgültige Zählung erhalten. 2 * q - p - 1 + 2 Operationen für diesen Algorithmus.
Dies ist eine lineare Funktion, da es keine Exponenten gibt, also die Wachstumsrate für unseren Summationsalgorithmus ist direkt gebunden an die Eingabe Größe, die wir nennen lineare Zeitkomplexität . In der Regel kennzeichnet der Term höchster Ordnung in einer Formel, die unsere Zeitkomplexität definiert, sein Wachstum im Laufe der Zeit. Wir nehmen also den Term höchster Ordnung und verschrotten den Rest, wobei q - p - 1 übrig bleibt.was wir nennen werden n der Einfachheit halber.
Die Komplexität der linearen Zeit klingt möglicherweise ineffizient, wenn Sie Eingabegrößen in Milliardenhöhe abbilden, aber die lineare Zeit ist eigentlich nicht schlecht. Wir können es jedoch besser machen.
Wir wissen schon sehr lange, dass die Summe von alle die Zahlen von 1 und q wird durch die Formel angegeben q * q + 1 / 2. Wir wissen auch, dass die kommutative Eigenschaft der Addition sagt uns, dass das Ergebnis von p-1 * p / 2 abgezogen von q * q + 1 / 2 springt einfach den Teil der Summe ab, der alles enthält von 1 zu p -1 verlässt das Summe der Zahlen von p zu q hinten, genau das wollen wir.
Dieser Algorithmus sollte je nach Codierung nicht länger dauern als drei Operationen. Da direkte mathematische Operationen wie diese genau das sind, was Computer besser können als Menschen, könnten wir die Formeln zu einem einzigen mathematischen Ausdruck zusammenfassen, und der Prozessor wird ihn so leicht durchkauen, wie wenn wir ihn in kleinere Teile zerlegen würden, aber wir bleiben bei drei Operationen für den Moment.
1. p = p-1 * p / 2
2. q = q * q + 1 / 2
3. zurück q - p
Nein Schleifen nur eine konstante Anzahl von Operationen, die sich nicht ändern, unabhängig vom Unterschied zwischen p und q ist. Dieser Algorithmus benötigt immer drei Operationen, also nennen wir das konstante zeitliche Komplexität .
Nun, wenn Sie nicht wussten, was Ihre Eingabegröße sollte es sein, als Sie einen Algorithmus entwarfen, welchen Algorithmus werden Sie zwischen diesen beiden verwenden? Offensichtlich der zweiter , weil Algorithmen mit konstanter Zeit sind im Wesentlichen a rechnerfreies Mittagessen, was die Eingabe betrifft. So wie wir vergrößern unser Programm zu handhaben weitere Daten , ihre Laufzeit wird sich nicht nennenswert ändern, während wir wissen, dass unser erster Algorithmus genau so stark wächst wie unsere Eingabe, was ein Wert in Milliardenhöhe oder mehr sein kann. Natürlich bedeutet konstante Zeitkomplexität nicht immer mehreffizient, aber in diesem Fall ist es das, was wir wollen.
Bevor wir uns jemals hinsetzten, um a zu schreiben Codezeile wir haben bereits herausgefunden, welcher Algorithmus war die bessere Option für unsere Eingabe und wir mussten es nie ausführen um herauszufinden, wie gut es funktioniert. Deshalb verwenden wir zeitliche Komplexität Es gibt einfach nicht so viele Tools, die so effektiv sind Bewertung der Effizienz von Algorithmen .
Was ist Big O-Notation?
Wir haben eine spezielle Möglichkeit, diese Effizienz zu kommentieren, um die Dinge zu vereinfachen, was wir nennen Big O-Notation . Einfach ausgedrückt, Big O-Notation repräsentiert die Algorithmen Effizienz durchlaufen Worst-Case-Szenario . Wenn Sie nach einem Namen in einem Verzeichnis suchen müssten, indem Sie jeden Namen lesen, bis Sie den richtigen gefunden haben, ist das schlimmste Szenario, dass der gewünschte Name der allerletzte Eintrag im Verzeichnis ist. Dies bedeutet, dass Sie einen habendas gesamte Verzeichnis von durchlesen n Namen, um zu dem gewünschten zu gelangen. Wir sagen also, dieser Algorithmus ist O n , wo n ist das Laufzeit höchster Ordnung in unserer Betriebsformel.
Es gibt andere Große Notationen für die bester Fall und Durchschnittsfall , aber was wirklich zählt, ist das Worst-Case-Szenario ; Dies sind diejenigen, die Ihren Computer zum Absturz bringen können - oder schlimmer noch Ihr Auto oder Ihr Flugzeug . Sie gehen genau ins Herz des Warum zeitliche Komplexität wichtig und zeigen Sie warum einige Algorithmen kann ein Problem einfach nicht lösen, ohne es zu nehmen einige Milliarden Jahre um es zu tun.
Wie verwenden wir Big O-Notation ? Die obige Tabelle zeigt Ihnen, wie sich diese unterscheiden Big O Notations siehe in der Praxis mit dem x-Achse als Ihre Eingabe und Ihre y-Achse die Zeit bis zum Ende. Für ein bisschen mehr Details finden Sie eine kurze Liste aller Big O Notations das ist jetzt wichtig und das zeitliche Komplexität sie repräsentieren :
* O 1 : Konstante Zeitkomplexität - Dies ist der effektiv rechnerische Freipass, über den wir zuvor gesprochen haben. Dies bedeutet nicht unbedingt, dass es schneller ist . Es bedeutet nur, dass die zeitliche Komplexität hängt nicht von der Größe des Eingangs ab.
* O log n : Logarithmische Zeitkomplexität - Diese sind am häufigsten bei Verwendung von a Divide-and-Conquer-Strategie in einem Datensatz, in dem bei jeder Operation ein großer Teil der Eingabe, bei der ausgeschlossen wurde, dass die Lösung nicht vorhanden ist. Das klassische Beispiel ist das Nachschlagen eines Wortes in einem Wörterbuch: Öffnen Sie es nach dem Zufallsprinzip, überprüfen Sie, in welchem Buchstabenabschnitt Sie sich befinden, und ignorieren Sie dann den Teil, in dem Sie wissen, dass Ihr Wort gewonnen hat. 't sein, und rekursiv unterteilen und verwerfen Sie die verbleibenden Abschnitte, bis Sie Ihr Wort finden.
* O n : lineare Zeitkomplexität - Dies war von Anfang an unser Summationsalgorithmus.
* O n log n : Linearithmische Zeitkomplexität - Eine schnelle Fourier-Transformation durchzuführen ist eine O n Log n Algorithmus wie a Mergesort .
* O n 2 : Quadratische Zeitkomplexität - Dies wird normalerweise immer dann gefunden, wenn Sie verschachtelte Schleifen haben. Wenn wir in unserem ersten Algorithmus eine zweite Schleife innerhalb der ersten Schleife hätten, hätte die Funktion eine quadratische Zeitkomplexität entwickelt. .
* O n c , c> 1 : Polynomzeitkomplexität - Polynomzeitkomplexität ist sehr wichtig weil es mehr oder weniger repräsentiert die Obergrenze auf was a klassischer Computer kann in praktischer Zeit gelöst werden.
* O c n , n> 1, c> 1 : Exponentielle Zeitkomplexität - Hier fangen Sie an, das zu bekommen Milliarden-Jahres-Algorithmen . Jederzeit a Eingabeeinheit veranlasst Sie doppelte Anzahl der durchgeführten Operationen relativ zur Anzahl der durchgeführten wenn der Eingang ist n-1 haben Sie exponentielle Zeitkomplexität . Das häufigste Beispiel, das die meisten Leute verwenden, ist das Aufzählen jede mögliche Teilmenge einer Menge , aber Brute-Forcing a 128-Bit-Verschlüsselungsschlüssel wird normalerweise in diese Kategorie eingeordnet.
* O n! : faktorielle Zeitkomplexität - Dies sind Algorithmen, die wahrscheinlich bis zum ausgeführt werden könnten. Hitzetod des Universums bei einer mäßig großen Eingabegröße von einigen Tausend. Wenn Sie so etwas wie "Wie viele verschiedene Möglichkeiten können Sie diese Sequenz anordnen" haben, haben Sie ein Permutationsproblem und das brutale Erzwingen des Weges zu einer Antwort erfordert das Erstellen. n! verschiedene Werte, die sich aus dem Ergebnis ergeben : n * n - 1 * n - 2 * ... * 3 * 2 * 1 . Dies sind die Algorithmen, die fast parallel zum laufen. y-Achse im obigen Diagramm.
Warum wir nicht einfach bessere Algorithmen finden können
Es ist nicht aus Mangel an Versuchen. Das gesamte Gebiet von theoretische Informatik dreht sich alles darum, das Beste zu finden effizienter Algorithmus für ein bestimmtes Problem, aber manchmal kennen wir die Mathematik einfach nicht. Und nicht nur Sie und ich, wir reden Field's Medal Gewinner die auf einige Probleme wie das gestoßen sind O 2 n und O n! und ihre Vermutung ist so gut wie unsere.
Es gibt eine ganze Reihe von Problemen, die wir noch nicht lösen können - wir werden uns gegen Ende der Serie näher damit befassen -, aber diese Probleme wirken als Engpässe, die zu Ineffizienzen in der Wirtschaft und in der wissenschaftlichen Forschung führen.und anderen Verwaltungsbereichen, und es gibt viele Leute, die darauf warten, dass diese Probleme endlich gelöst werden. Sehr lukrative Preise wurden sogar jedem angeboten Wer kann einige dieser Dinge lösen, aber bisher hat es niemand geschafft und einige dieser Probleme haben jahrzehntelang herumgesessen.
Der Grund warum klassische Computer Diese Probleme können auch nicht effizient gelöst werden. Sie sind in die Schaltkreise der Maschine integriert. Jede erteilte Anweisung muss ausgeführt werden, bevor sie mit der nächsten beginnen kann. Multicore-Systeme oder Multiprozessor-Maschinen können die Dinge beschleunigen, aber Sie würden sie wahrscheinlich noch brauchen ein oder zwei Billionen Jahre um ein Ergebnis zu erzielen, nachdem Sie alle unsere Prozessoren zusammengeschmissen und auf einem gelöst haben O n! Problem wo n war so etwas wie 500 .
Computeringenieure haben dies kommen sehen seit Jahrzehnten , aber jetzt kommen wir endlich zum Ende der Reihe für das, was wir aus a herausdrücken können klassischer Computer . Sie können diese einfach nicht machen Operationen gehen schneller und von Natur aus können sie jeweils nur eine Operation ausführen . Wenn Sie einen Algorithmus haben, der dies erfordert Billionen von Operationen zum Abschluss a klassischer Computer muss all diese ausführen Operationen in Reihenfolge. An diesem Punkt ist die Zeit, die benötigt wird, um ein Ergebnis zu erhalten, einfach eine Frage von Mathematik und Physik . Wenn wir diese Probleme lösen wollen, die haben exponentielle Zeitkomplexität oder höher dann etwas anderes wird benötigt.
Die gute Nachricht ist, dass wir wissen, dass es möglich ist, in mindestens ein Fall um einen Algorithmus zu finden, der effizient genug ist, um die Antwort auf eine dieser Fragen zu finden O 2 n Probleme in Polynomzeitkomplexität . Wenn es einmal gemacht werden kann, ist es möglich, es wieder zu machen; es dauert nur umgeht die ganze "Physik" Sache .
Der vierte Artikel in unserer Reihe über Algorithmen und Berechnungen Wie der Algorithmus von Peter Shor die RSA-Verschlüsselung zum Scheitern verurteilt, kann gefunden werden hier .