[Powered by Google Translate] Wahrscheinlich haben Sie gehört, wie Leute reden über eine schnelle oder effizienten Algorithmus für die Ausführung Ihrer bestimmte Aufgabe, aber was genau bedeutet es für einen Algorithmus, um schnell oder effizient bedeuten? Nun, es ist nicht um eine Messung in Echtzeit wie Sekunden oder Minuten. Dies liegt daran, Computer-Hardware und Software variieren drastisch. Mein Programm könnte langsamer laufen als du, weil ich es läuft auf einem älteren Computer, oder weil ich zufällig spielen ein Online-Videospiel zur gleichen Zeit, ist die Beschlag all meiner Erinnerung, oder ich könnte ausgeführt werden, mein Programm durch verschiedene Software- die Kommunikation mit dem System unterschiedlich auf einem niedrigen Niveau. Es ist wie Äpfel mit Birnen vergleichen. Nur weil meine langsameren Computer dauert länger als deins zurück zu geben eine Antwort bedeutet nicht, haben Sie die effizienter Algorithmus. 

Also, da können wir nicht direkt vergleichen die Laufzeiten der Programme in Sekunden oder Minuten, Wie können wir vergleichen 2 verschiedene Algorithmen unabhängig von ihrer Hardware-oder Software-Umgebung? Um eine einheitliche Methode zur Messung der algorithmischen Effizienz zu schaffen, Informatikern und Mathematikern entworfen haben Konzepte zur Messung des asymptotischen Komplexität eines Programms und eine Notation namens "Big Ohnotation ' zur Beschreibung dieser. Die formale Definition ist, dass eine Funktion f (x) läuft in der Größenordnung von g (x) falls es einige (x)-Wert, x ₀ und eine Konstante, C, für welche f (x) weniger als oder gleich daß Konstante mal g (x) für alle x größer als x ₀. 

Aber nicht weg von der formalen Definition Angst. Was bedeutet das eigentlich in weniger theoretische Begriffe bedeuten? Nun, es ist im Grunde eine Art der Analyse Wie schnell ein Programm zur Laufzeit asymptotisch wächst. Das heißt, wie die Größe der Eingänge erhöht gegen unendlich, sagen, du bist Sortieren eines Arrays der Größe 1000 im Vergleich zu einem Array der Größe 10. Wie wirkt sich die Laufzeit Ihres Programms wachsen? Zum Beispiel vorstellen, Zählen der Anzahl von Zeichen in einem String der einfachste Weg  zu Fuß durch die ganze Reihe letter-by-letter und Zugabe von 1 zu einem Zähler für jedes Zeichen. Dieser Algorithmus soll in linearer Zeit ausgeführt werden in Bezug auf die Anzahl der Zeichen, "N" in der Zeichenfolge. Kurz gesagt, es läuft in O (n). Woran liegt das? Nun, mit diesem Ansatz die erforderliche Zeit die gesamte Zeichenfolge durchlaufen proportional zu der Anzahl von Zeichen. Zählen der Anzahl von Zeichen in einem 20-Zeichenkette wird doppelt so lange dauern, wie es dauert um die Zeichen in eine 10-stellige Zeichenkette zu zählen, denn man muss an allen Zeichen sehen und jedes Zeichen tritt die gleiche Menge an Zeit, zu betrachten. Wie erhöhen Sie die Anzahl der Zeichen, die Laufzeit steigt linear mit dem Eingang Länge. 

Nun, wenn Sie sich vorstellen, dass die lineare Zeit zu entscheiden, O (n), war einfach nicht schnell genug für Sie? Vielleicht hast du Speicherung großer Streicher, und Sie können es sich nicht leisten die zusätzliche Zeit es dauern würde, aller zugehörigen Zeichen Zählen einer nach dem ein zu durchqueren. So entscheiden Sie sich etwas anderes ausprobieren. Was, wenn Sie passieren würde schon speichern die Anzahl der Zeichen im String, sagen wir, in einer Variable namens 'len' frühzeitig in das Programm, bevor man überhaupt das erste Zeichen in der Zeichenfolge gespeichert? Dann, müsstest du jetzt tun, um herauszufinden, die String-Länge, wird prüfen, was der Wert der Variablen ist. Sie würden nicht an der Schnur selbst überhaupt aussehen, und Zugreifen auf den Wert einer Variablen wie len gilt asymptotisch konstanter Zeit Betrieb oder O (1). Woran liegt das? Nun, daran erinnern, was asymptotische Komplexität bedeutet. Wie funktioniert die Laufzeit Veränderung der Größe Ihrer Eingaben wächst? 

Angenommen, Sie haben versucht, die Anzahl der Zeichen in einer größeren Zeichenfolge zu erhalten. Nun, ich würde es keine Rolle, wie groß Sie die Zeichenfolge zu machen, sogar eine Million Zeichen lang sein, alles, was Sie würde tun müssen, um Länge der Zeichenfolge mit diesem Ansatz zu finden, ist zum Auslesen der Wert der Variablen len, die Sie bereits gemacht. Der Eingang Länge, das heißt, die Länge der Zeichenfolge, die Sie versuchen zu finden sind, überhaupt nicht, wie schnell Ihr Programm läuft beeinflussen. Dieser Teil des Programms würde gleich schnell laufen auf einem ein-Zeichenkette und tausend-Zeichenkette, und das ist, warum dieses Programm würde als laufen in konstanter Zeit bezeichnet werden mit Bezug auf die Eingangsspannung skalieren. 

Natürlich gibt es einen Nachteil. Sie verbringen mehr Speicherplatz auf Ihrem Computer Speichern der variablen und die zusätzliche Zeit, die Sie um die eigentliche Lagerung des variablen tun, aber der Punkt steht noch, herauszufinden, wie lange Ihr String war nicht von der Länge der Zeichenfolge überhaupt abhängen. So läuft es in O (1) oder konstante Zeit. Das bedeutet natürlich nicht bedeuten muss, dass Ihr Code läuft in 1 Schritt aber egal, wie viele Schritte es ist, wenn es nicht mit der Größe der Inputs zu ändern, es ist immer noch asymptotisch Konstante, die wir vertreten als O (1). 

Wie Sie wahrscheinlich erraten, es gibt viele verschiedene große O Laufzeiten von Algorithmen mit messen. O (n) ² Algorithmen sind asymptotisch langsamer als O (n)-Algorithmen. Das heißt, wie die Anzahl der Elemente (n) wächst, schließlich O (n) ²-Algorithmen wird mehr Zeit als O (n)-Algorithmen zu laufen. Dies bedeutet nicht, O (n)-Algorithmen immer schneller laufen als O (n) ²-Algorithmen, sogar in der gleichen Umgebung, auf der gleichen Hardware. Vielleicht für kleine Eingangs-Größen  O (n) ²-Algorithmus könnte in der Tat schneller zu arbeiten, aber schließlich als Eingang vergrößernden gegen unendlich, der O (n) ² Algorithmus Laufzeit schließlich verdunkeln die Laufzeit des O (n)-Algorithmus. Genau wie jede quadratische mathematische Funktion  schließlich überholen jede lineare Funktion, egal wie viel von einem Vorsprung der linearen Funktion beginnt mit. Wenn Sie mit großen Datenmengen arbeiten, Algorithmen, die in O laufen (n) ² Zeit wirklich am Ende verlangsamt Ihr Programm, aber für kleine Eingangs-Größen Sie werden wahrscheinlich nicht einmal bemerken. 

Ein weiterer asymptotische Komplexität ist, logarithmischer Zeit, O (log n). Ein Beispiel für einen Algorithmus, der diese läuft schnell ist die klassische binäre Suchalgorithmus, zum Finden eines Elements in einer bereits sortierten Liste von Elementen. 

Wenn Sie nicht wissen, was binäre Suche tut, Ich werde es für Sie sehr schnell zu erklären. Angenommen, Sie sind für die Zahl 3 suchen in diesem Array von ganzen Zahlen. Es sieht am mittleren Element des Arrays und fragt: "Ist das Element Ich will größer, gleich oder kleiner als diese?" Wenn es gleich, dann groß. Sie haben das Element, und du bist fertig. Wenn es größer ist, dann wissen Sie das Element hat, um in der rechten Seite der Anordnung ist, und man kann nur an, dass in Zukunft aussehen, und wenn es kleiner ist, dann wissen Sie, es muss auf der linken Seite sein. Dieser Prozess wird dann mit der kleinerer Größe Array wiederholt bis das richtige Element gefunden wird. 

Diese leistungsfähigen Algorithmus schneidet die Array-Größe in der Hälfte mit jeder Operation. Also, um ein Element in einem sortierten Array der Größe 8 zu finden, höchstens (log ₂ 8), oder 3 dieser Operationen, Prüfen der mittleren Element, dann Schneiden des Array in der Hälfte benötigt werden, während ein Array der Größe 16 nimmt (log ₂ 16), oder 4 Operationen. Das ist nur ein weitere Operation für eine verdoppelte-size Array. Eine Verdoppelung der Größe des Arrays erhöht die Laufzeit von nur 1 Stück dieses Codes. Auch die Überprüfung der mittleren Element der Liste, dann spalten. Also, es ist gesagt, in logarithmischer Zeit zu betreiben, O (log n). Aber warten Sie, sagen Sie, nicht davon abhängen, wo in der Liste das Element Sie suchen ist? Was ist, wenn das erste Element man sich zufällig der richtige sein? Dann dauert es nur 1-Betrieb, egal wie groß die Liste ist. 

Nun, das ist, warum Informatiker mehr Begriffe haben für asymptotische Komplexität aus, die best-case reflektieren und Worst-Case Leistungen eines Algorithmus. Besser gesagt der obere und untere Schranken auf die Laufzeit. Im besten Fall für die binäre Suche, ist unser Element genau dort in der Mitte, und Sie erhalten es in konstanter Zeit, egal wie groß der Rest des Feldes ist. Das Symbol hierfür verwendet wird, ist Ω. Ja, wird dieser Algorithmus in der Ω (1) laufen. Im besten Fall, findet es das Element schnell, egal wie groß das Array ist, aber im schlimmsten Fall, es zu erfüllen hat (log n) split Schecks des Arrays finden Sie die richtige Element. Worst-case obere Schranken sind mit dem großen "O", dass Sie bereits wissen, bezeichnet. Also, es ist O (log n), aber Ω (1). 

Eine lineare Suche hingegen in dem Sie zu Fuß durch jedes Element des Arrays um das gewünschte zu finden, ist bestenfalls Ω (1). Auch das erste Element, das Sie wollen. So spielt es keine Rolle, wie groß das Array ist. Im ungünstigsten Fall ist es das letzte Element in dem Array. Also, haben Sie durch alle n Elemente im Array gehen, es zu finden, wie wenn Sie für ein 3-suchten. So läuft es in O (n) Zeit denn es ist proportional zu der Anzahl der Elemente in dem Array. 

Eine weitere verwendete Symbol ist Θ. Dies kann verwendet werden, um Algorithmen, wo die besten und schlimmsten Fall zu beschreiben gleich sind. Dies ist der Fall in den string-length Algorithmen, die wir vorhin gesprochen haben. Das heißt, wenn wir sie in einer Variablen vor speichern wir den String und greifen später in konstanter Zeit. Egal, welche Zahl wir in dieser Variablen speichern, haben wir es zu betrachten. Der beste Fall ist, betrachten wir es und finden Sie die Länge des Strings. So Ω (1) oder günstigsten Fall konstante Zeit. Der schlimmste Fall ist, wir es betrachten und finden Sie die Länge des Strings. Also, O (1) oder konstante Zeit im schlimmsten Fall. So, da im besten Fall und schlimmsten Fällen die gleichen sind, Dies kann gesagt werden, dass in Θ (1) Zeit laufen. 

Zusammenfassend haben wir gute Möglichkeiten, an die Vernunft über Codes Effizienz ohne zu wissen, nichts über die realen Zeit nehmen sie zu laufen, Welches ist von vielen äußeren Faktoren beeinflusst, einschließlich unterschiedlicher Hardware, Software, oder die Besonderheiten Ihres Codes. Außerdem ermöglicht es uns, auch die Vernunft über das, was geschehen wird, wenn die Größe der Ein-zunimmt. 

Wenn Sie in O (n) ²-Algorithmus läuft, oder noch schlimmer, ein O (2 ⁿ)-Algorithmus, einer der am schnellsten wachsenden Arten, Sie wirklich anfangen, die Verlangsamung bemerken, Wenn Sie die Arbeit mit größeren Datenmengen zu starten. 

Das ist asymptotische Komplexität. Thanks.