Eine Einführung in die zeitliche Komplexität von Algorithmen

In der Informatik spielt die Analyse von Algorithmen eine sehr wichtige Rolle. Es ist wichtig, den effizientesten Algorithmus zur Lösung eines Problems zu finden. Es ist möglich, viele Algorithmen zur Lösung eines Problems zu haben, aber die Herausforderung besteht darin, den effizientesten auszuwählen.

Nun geht es darum, wie wir den effizientesten Algorithmus erkennen können, wenn wir eine Reihe verschiedener Algorithmen haben. Hier entsteht das Konzept der räumlichen und zeitlichen Komplexität von Algorithmen. Die räumliche und zeitliche Komplexität dient als Messskala für Algorithmen. Wir vergleichen die Algorithmen anhand ihres Raums (Speichermenge) und ihrer Zeitkomplexität (Anzahl der Operationen).

Die Gesamtmenge des Computerspeichers, die von einem Algorithmus bei seiner Ausführung verwendet wird, ist die räumliche Komplexität dieses Algorithmus. Wir werden in diesem Artikel nicht auf die Komplexität des Speicherplatzes eingehen (um diesen Artikel etwas kleiner zu machen).

Zeitliche Komplexität

Die zeitliche Komplexität ist also die Anzahl der Operationen, die ein Algorithmus ausführt, um seine Aufgabe abzuschließen (wenn man bedenkt, dass jede Operation dieselbe Zeit benötigt). Der Algorithmus, der die Aufgabe in der kleinsten Anzahl von Operationen ausführt, wird hinsichtlich der zeitlichen Komplexität als der effizienteste angesehen. Die räumliche und zeitliche Komplexität wird jedoch auch von Faktoren wie Ihrem Betriebssystem und Ihrer Hardware beeinflusst, die wir jedoch nicht in diese Diskussion einbeziehen.

Um die zeitliche Komplexität zu verstehen, nehmen wir ein Beispiel, in dem wir zwei verschiedene Algorithmen vergleichen, die zur Lösung eines bestimmten Problems verwendet werden.

Das Problem ist die Suche. Wir müssen nach einem Element in einem Array suchen (in diesem Problem gehen wir davon aus, dass das Array in aufsteigender Reihenfolge sortiert ist). Um dieses Problem zu lösen, haben wir zwei Algorithmen:

1. Lineare Suche.

2. Binäre Suche.

Angenommen, das Array enthält zehn Elemente, und wir müssen die Nummer zehn im Array finden.

const array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; const search_digit = 10;

Der lineare Suchalgorithmus vergleicht jedes Element des Arrays mit der Suchnummer . Wenn das search_digit im Array gefunden wird, wird true zurückgegeben .

Zählen wir nun die Anzahl der durchgeführten Operationen. Hier lautet die Antwort 10 (da jedes Element des Arrays verglichen wird). Die lineare Suche verwendet also zehn Operationen, um das angegebene Element zu finden (dies ist die maximale Anzahl von Operationen für dieses Array; im Fall der linearen Suche wird dies auch als der schlechteste Fall eines Algorithmus bezeichnet).

Im Allgemeinen benötigt die lineare Suche im schlimmsten Fall n Operationen (wobei n die Größe des Arrays ist).

Lassen Sie uns den binären Suchalgorithmus für diesen Fall untersuchen.

Die binäre Suche kann anhand dieses Beispiels leicht verstanden werden:

Quelle: Learneroo

Wenn wir versuchen, diese Logik auf unser Problem anzuwenden, vergleichen wir zuerst search_digit mit dem mittleren Element des Arrays, dh 5. Da 5 kleiner als 10 ist, suchen wir in den Array-Elementen nach search_digit größer als 5, auf die gleiche Weise, bis wir das gewünschte Element 10 erhalten.

Versuchen Sie nun, die Anzahl der Operationen zu zählen, die die binäre Suche ausgeführt hat, um das gewünschte Element zu finden. Es dauerte ungefähr vier Operationen. Dies war der schlimmste Fall für die binäre Suche. Dies zeigt, dass es eine logarithmische Beziehung zwischen der Anzahl der ausgeführten Operationen und der Gesamtgröße des Arrays gibt.

Anzahl der Operationen = log (10) = 4 (ungefähr)

für Basis 2

Wir können dieses Ergebnis für die binäre Suche wie folgt verallgemeinern:

Für ein Array der Größe n beträgt die Anzahl der von der binären Suche ausgeführten Operationen: log (n)

Die Big O-Notation

In den obigen Anweisungen haben wir gesehen, dass für ein Array der Größe n die lineare Suche n Operationen ausführt , um die Suche abzuschließen. Andererseits führte die binäre Suche eine log (n) Anzahl von Operationen durch (beide für ihre schlimmsten Fälle). Wir können dies als Diagramm darstellen ( x-Achse : Anzahl der Elemente, y-Achse : Anzahl der Operationen).

Quelle: Techtud

Aus der Abbildung geht klar hervor, dass die Geschwindigkeit, mit der die Komplexität bei der linearen Suche zunimmt, viel schneller ist als bei der binären Suche.

Wenn wir einen Algorithmus analysieren, verwenden wir eine Notation, um seine zeitliche Komplexität darzustellen, und diese Notation ist die Big O-Notation.

Zum Beispiel: Die Zeitkomplexität für die lineare Suche kann als O (n) und O (log n) für die binäre Suche dargestellt werden (wobei n und log (n) die Anzahl der Operationen sind).

Die Zeitkomplexität oder Big O-Notationen für einige gängige Algorithmen sind nachstehend aufgeführt:

  1. Binäre Suche: O (log n)
  2. Lineare Suche: O (n)
  3. Schnelle Sortierung: O (n * log n)
  4. Auswahl Sortieren: O (n * n)
  5. Reisender Verkäufer: O (n!)

Fazit

Ich freue mich sehr über Ihre Bemühungen, wenn Sie diesen Artikel noch lesen. Jetzt müssen Sie sich überlegen, warum es so wichtig ist, Zeitkomplexität zu verstehen.

Wir wissen, dass für eine kleine Anzahl von Elementen (z. B. 10) der Unterschied zwischen der Anzahl der durch die binäre Suche und die lineare Suche ausgeführten Operationen nicht so groß ist. In der realen Welt beschäftigen wir uns jedoch meistens mit Problemen mit großen Datenmengen.

Wenn wir beispielsweise 4 Milliarden Elemente suchen müssen, benötigt die lineare Suche im schlimmsten Fall 4 Milliarden Operationen, um ihre Aufgabe zu erfüllen. Die binäre Suche erledigt diese Aufgabe in nur 32 Vorgängen. Das ist ein großer Unterschied. Nehmen wir nun an, wenn eine Operation 1 ms dauert, dauert die binäre Suche nur 32 ms, während die lineare Suche 4 Milliarden ms dauert (das sind ca. 46 Tage). Das ist ein bedeutender Unterschied.

Dies ist der Grund, warum das Studium der Zeitkomplexität wichtig wird, wenn es um eine so große Datenmenge geht.

Ressourcen

Grokking-Algorithmen - von Aditya Y Bhargava

Einführung in die Big O-Notation und Zeitkomplexität - von CS Dojo