Was ist Big-O-Notation?

Haben Sie sich jemals gefragt, warum die Ausführung eines von Ihnen geschriebenen Programms so lange gedauert hat? Vielleicht möchten Sie wissen, ob Sie Ihren Code effizienter gestalten können. Wenn Sie wissen, wie Code ausgeführt wird, können Sie Ihren Code auf die nächste Ebene bringen. Die Big-O-Notation ist ein praktisches Tool, um zu berechnen, wie effizient Ihr Code wirklich ist.

Was ist Big-O-Notation?

Mit der Big-O-Notation können Sie berechnen, wie lange es dauert, bis Ihr Code ausgeführt wird. Sie können physisch festlegen, wie lange die Ausführung Ihres Codes dauert. Mit dieser Methode ist es jedoch schwierig, kleine Zeitunterschiede zu erkennen. Beispielsweise ist die Zeit zwischen 20 und 50 Codezeilen sehr gering. In einem großen Programm können sich diese Ineffizienzen jedoch summieren.

Die Big-O-Notation zählt, wie viele Schritte ein Algorithmus ausführen muss, um seine Effizienz zu messen. Die Annäherung an Ihren Code auf diese Weise kann sehr effektiv sein, wenn Sie Ihren Code optimieren müssen, um die Effizienz zu steigern. Mit der Big-O-Notation können Sie verschiedene Algorithmen anhand der Anzahl der Schritte messen, die zum Ausführen erforderlich sind, und die Effizienz der Algorithmen objektiv vergleichen.

Wie berechnet man die Big-O-Notation?

Betrachten wir zwei Funktionen, die zählen, wie viele einzelne Socken sich in einer Schublade befinden. Jede Funktion nimmt die Anzahl der Sockenpaare und gibt die Anzahl der einzelnen Socken zurück. Der Code ist in Python geschrieben, aber das hat keinen Einfluss darauf, wie wir die Anzahl der Schritte zählen würden.

Algorithmus 1:

def sockCounter (numberOfPairs):
individualSocks = 0
für x im Bereich (numberOfPairs):
individualSocks = individualSocks + 2
individualSocks zurückgeben

Algorithmus 2:

def sockCounter (numberOfPairs):
return numberOfPairs * 2

Dies ist ein dummes Beispiel, und Sie sollten leicht erkennen können, welcher Algorithmus effizienter ist. Aber zum Üben lassen Sie uns jeden durchgehen.

VERBUNDEN: Was ist eine Funktion in der Programmierung?

Was ist eine Funktion in der Programmierung?

Wenn Sie lernen, wie Sie Ihren eigenen Code programmieren, müssen Sie die Funktionen verstehen.

Algorithmus 1 hat viele Schritte:

1. Der Variablen individualSocks wird der Wert Null zugewiesen.
2. Es weist der Variablen i den Wert Eins zu.
3. Es vergleicht den Wert von i mit numberOfPairs.
4. Es werden zwei zu individualSocks hinzugefügt.
5. Es weist sich den erhöhten Wert von individualSocks zu.
6. Es erhöht i um eins.
7. Anschließend werden die Schritte 3 bis 6 genauso oft wie in (indiviualSocks - 1) durchlaufen.

Die Anzahl der Schritte, die wir für den ersten Algorithmus ausführen müssen, kann ausgedrückt werden als:

4n + 2

Es gibt vier Schritte, die wir n Mal ausführen müssen. In diesem Fall würde n dem Wert von numberOfPairs entsprechen. Es gibt auch 2 Schritte, die einmal ausgeführt werden.

Im Vergleich dazu hat Algorithmus 2 nur einen Schritt. Der Wert von numberOfPairs wird mit zwei multipliziert. Wir würden das ausdrücken als:

1

Wenn es nicht schon offensichtlich war, können wir jetzt leicht erkennen, dass Algorithmus 2 um einiges effizienter ist.

Big-O-Analyse

Wenn Sie an der Big-O-Notation eines Algorithmus interessiert sind, interessieren Sie sich im Allgemeinen mehr für die Gesamteffizienz und weniger für die Feinkornanalyse der Anzahl der Schritte. Um die Notation zu vereinfachen, können wir nur die Größe der Effizienz angeben.

In den obigen Beispielen würde Algorithmus 2 als eins ausgedrückt:

O (1)

Algorithmus 1 würde jedoch wie folgt vereinfacht:

Auf)

Dieser kurze Schnappschuss zeigt uns, wie die Effizienz des Algorithmus eins an den Wert von n gebunden ist. Je größer die Anzahl, desto mehr Schritte muss der Algorithmus ausführen.

Linearer Code

Da wir den Wert von n nicht kennen, ist es hilfreicher darüber nachzudenken, wie sich der Wert von n auf die Menge an Code auswirkt, die ausgeführt werden muss. In Algorithmus 1 können wir sagen, dass die Beziehung linear ist. Wenn Sie die Anzahl der Schritte vs. Mit dem Wert von n erhalten Sie eine gerade Linie, die nach oben geht.

Quadratischer Code

Nicht alle Beziehungen sind so einfach wie das lineare Beispiel. Stellen Sie sich vor, Sie haben ein 2D-Array und möchten nach einem Wert im Array suchen. Sie können einen Algorithmus wie den folgenden erstellen:

def searchForValue (targetValue, arraySearched):
foundTarget = False
für x in arraySearched:
für y in x:
if (y == targetValue):
foundTarget = True
return foundTarget

In diesem Beispiel hängt die Anzahl der Schritte von der Anzahl der Arrays in arraySearched und der Anzahl der Werte in jedem Array ab. Die vereinfachte Anzahl von Schritten wäre also n * n oder n².

Diese Beziehung ist eine quadratische Beziehung, was bedeutet, dass die Anzahl der Schritte in unserem Algorithmus exponentiell mit n wächst. In der Big-O-Notation würden Sie es schreiben als:

O (n²)

VERBUNDEN: Nützliche Tools zum Überprüfen, Bereinigen und Optimieren von CSS-Dateien

Logarithmischer Code

Obwohl es viele andere Beziehungen gibt, werden wir uns zuletzt mit logarithmischen Beziehungen befassen. Um Ihren Speicher aufzufrischen, ist das Protokoll einer Zahl der Exponentenwert, der erforderlich ist, um eine Zahl mit einer bestimmten Basis zu erreichen. Zum Beispiel:

log 2 (8) = 3

Das Protokoll ist gleich drei, denn wenn unsere Basis 2 wäre, würden wir einen Exponentenwert von 3 benötigen, um zur Zahl 8 zu gelangen.

Die Beziehung einer logarithmischen Funktion ist also das Gegenteil einer exponentiellen Beziehung. Wenn n zunimmt, sind weniger neue Schritte erforderlich, um den Algorithmus auszuführen.

Auf den ersten Blick scheint dies nicht intuitiv zu sein. Wie können die Schritte eines Algorithmus langsamer als n werden? Ein gutes Beispiel hierfür ist die binäre Suche. Betrachten wir einen Algorithmus zum Suchen nach einer Zahl in einem Array eindeutiger Werte.

• Wir beginnen mit einem zu suchenden Array, das in der Reihenfolge vom kleinsten zum größten liegt.
• Als nächstes überprüfen wir den Wert in der Mitte des Arrays.
• Wenn Ihre Nummer höher ist, schließen wir die niedrigeren Nummern in unserer Suche aus, und wenn die Nummer niedriger war, schließen wir die höheren Nummern aus.
• Nun werden wir uns die mittlere Zahl der verbleibenden Zahlen ansehen.
• Auch hier schließen wir die Hälfte der Zahlen aus, je nachdem, ob unser Zielwert höher oder niedriger als der Mittelwert ist.
• Wir werden diesen Prozess fortsetzen, bis wir unser Ziel gefunden haben oder feststellen, dass es nicht in der Liste enthalten ist.

Wie Sie sehen können, wird die Auswirkung auf die Häufigkeit, mit der wir das Array überprüfen, kaum beeinflusst, da durch binäre Suchen bei jedem Durchgang die Hälfte der möglichen Werte eliminiert wird. Um dies in Big-O-Notation auszudrücken, würden wir schreiben:

O (log (n))

Die Bedeutung der Big-O-Notation

Mit Big-O Nation können Sie schnell und einfach kommunizieren, wie effizient ein Algorithmus ist. Dies erleichtert die Entscheidung zwischen verschiedenen Algorithmen. Dies kann besonders hilfreich sein, wenn Sie einen Algorithmus aus einer Bibliothek verwenden und nicht unbedingt wissen, wie der Code aussieht.

Wenn Sie zum ersten Mal das Codieren lernen, beginnen Sie mit linearen Funktionen. Wie Sie aus der obigen Grafik sehen können, werden Sie damit sehr weit kommen. Wenn Sie jedoch erfahrener werden und komplexeren Code erstellen, wird die Effizienz zu einem Problem. Wenn Sie wissen, wie Sie die Effizienz Ihres Codes quantifizieren können, erhalten Sie die Tools, die Sie benötigen, um ihn auf Effizienz abzustimmen und die Vor- und Nachteile von Algorithmen abzuwägen.

10 Häufigste Programmier- und Codierungsfehler

Codierungsfehler können zu so vielen Problemen führen. Diese Tipps helfen Ihnen, Programmierfehler zu vermeiden und Ihren Code aussagekräftig zu halten.

Über den Autor