Die Komplexität einfacher Algorithmen und Datenstrukturen in JS

Im vorherigen Artikel „Ein Schritt in Richtung Computing als Wissenschaft: Einfache Algorithmen und Datenstrukturen in JS“ haben wir einfache Algorithmen (lineare und binäre Suche; Blasen-, Auswahl- und Einfügesortierungen) und Datenstrukturen (Array- und Schlüsselwert-gepaarte Objekte) erörtert ). Hier fahre ich mit dem Konzept der Komplexität und seiner Anwendung auf diese Algorithmen und Datenstrukturen fort.

Komplexität

Komplexität ist ein Faktor, der in einen komplexen Prozess involviert ist. In Bezug auf Algorithmen und Datenstrukturen kann dies die Zeit oder der Raum (dh der Arbeitsspeicher) sein, die erforderlich sind, um eine bestimmte Aufgabe (Suchen, Sortieren oder Zugreifen auf Daten) für eine bestimmte Datenstruktur auszuführen. Die Effizienz der Ausführung einer Aufgabe hängt von der Anzahl der Vorgänge ab, die zum Ausführen einer Aufgabe erforderlich sind.

Das Herausnehmen des Mülls kann 3 Schritte erfordern (einen Müllsack zusammenbinden, nach draußen bringen und in einen Müllcontainer werfen). Das Herausnehmen des Mülls mag einfach sein, aber wenn Sie den Müll nach einer langen Woche der Renovierung herausnehmen, können Sie die Aufgabe möglicherweise aufgrund von Platzmangel im Müllcontainer nicht erledigen .

Das Staubsaugen eines Raums kann viele sich wiederholende Schritte erfordern (Einschalten, wiederholtes Streichen des Vakuumkopfs über einen Boden und Ausschalten). Je größer ein Raum ist, desto öfter müssen Sie einen Vakuumkopf über den Boden streichen. Je länger die Zeit dauert, um den Raum abzusaugen.

Es besteht also ein direkter Kausalzusammenhang zwischen der Anzahl der ausgeführten Operationen und der Anzahl der Elemente, die ausgeführt werden. Wenn Sie viel Müll (Elemente) haben, müssen Sie ihn viele Male herausnehmen. Dies kann zu einem Problem der Raumkomplexität führen . Wenn Sie viel Quadratmeter (Elemente) haben, müssen Sie einen Vakuumkopf mehrmals über einen Boden streichen. Dies kann zu einem Problem der Zeitkomplexität führen .

Unabhängig davon, ob Sie den Müll herausnehmen oder einen Raum staubsaugen , können Sie sagen, dass die Anzahl der Vorgänge ( O ) genau mit der Anzahl der Elemente ( n ) zunimmt . Wenn ich 1 Müllsack habe, muss ich den Müll einmal herausnehmen. Wenn ich 2 Müllsäcke hatte, muss ich dieselbe Aufgabe zweimal ausführen, vorausgesetzt, Sie können physisch nicht mehr als einen Sack gleichzeitig heben. Das Big-O dieser Aufgaben ist also O = n oder O = Funktion (n) oder O (n) . Dies ist eine lineare Komplexität (eine gerade Linie mit einer 1-Operation: 1-Element-Entsprechung). Es werden also 30 Operationen an 30 Elementen ausgeführt (gelbe Linie in der Grafik).

Dies ist ähnlich wie bei der Betrachtung von Algorithmen und Datenstrukturen.

Suchen

Lineare Suche

Der beste Fall für die Suche nach einem Artikel in einer geordneten Liste nacheinander ist eine Konstante O (1) , vorausgesetzt, es handelt sich um den ersten Artikel in Ihrer Liste. Wenn also der gesuchte Artikel unabhängig von Ihrer Listengröße immer zuerst aufgeführt wird, finden Sie Ihren Artikel sofort. Die Komplexität Ihrer Suche ist mit der Listengröße konstant. Der Durchschnitt bis zum schlimmsten Fall dieser Art der Suche ist eine lineare Komplexität oder O (n). Mit anderen Worten,Für n Artikel muss ich n Mal suchen, bevor ich meinen Artikel finde, daher lineare Suche.

Binäre Suche

Bei einer binären Suche ist der beste Fall O (1), was bedeutet, dass sich das Element Ihrer Suche im Mittelpunkt befindet. Der schlechteste und durchschnittliche Fall ist die logarithmische Basis 2 von n oder:

Logarithmus oder Log ist eine Möglichkeit, einen Exponenten für eine bestimmte Basis auszudrücken. Wenn es also 16 Elemente gäbe (n = 16), würde es im schlimmsten Fall 4 Schritte dauern, um die Zahl 15 zu finden (Exponent = 4).

Oder einfach: O (log n)

Sorten

Blase

Bei der Blasensortierung wird jedes Element mit dem Rest der Sammlung verglichen, um den höchsten Wert für das Aufblasen zu bestimmen. Aus diesem Grund beträgt seine Komplexität im Durchschnitt bis zum schlimmsten Fall O (n²) . Stellen Sie sich eine Schleife vor, die in einer anderen Schleife verschachtelt ist.

Sie vergleichen es also für jedes Objekt mit dem Rest Ihrer Sammlung. Dies entspricht 16 Vergleichen (oder Operationen) für 4 Elemente (4² = 16). Der beste Fall ist, wenn Ihre Sammlung bis auf einen einzelnen Artikel fast sortiert ist. Dies würde eine einzige Vergleichsrunde bedeuten. Das heißt, vier Vergleiche sind erforderlich, um ein Mitglied einer Sammlung mit vier Elementen in die Luft zu sprudeln, was eine Komplexität von O (n) darstellt .

Auswahl

Im Gegensatz zur Blasensortierung wählt die Auswahlsortierung nicht den höchsten Wert aus, sondern den niedrigsten Wert, um ihn an die frühesten Positionen zu verschieben. Da jedoch jedes Element mit dem Rest der Sammlung verglichen werden muss, hat es auch eine Komplexität von O (n²) .

Einfügen

Im Gegensatz zu den Blasen & Auswahl Sorten , Insertionsort fügt das Element in seine richtige Position. Wie bei den vorherigen Sortierungen muss jedoch auch jedes Element mit dem Rest der Sammlung verglichen werden. Daher weist es eine durchschnittliche bis schlechteste Komplexität von O (n²) auf . Wie bei der Blasensortierung ist nur eine einzige Vergleichsrunde erforderlich, um das Element an der richtigen Position einzufügen, wenn nur noch ein Element zu sortieren ist. Das heißt, es hat die Best-Case- Komplexität von O (n) .

Datenstrukturen

Arrays

Da der Zugriff auf ein Element eines Arrays über seinen Index in einem einzigen Schritt oder das Hinzufügen / Entfernen eines Elements am Ende eines Arrays erforderlich ist , beträgt die Komplexität für den Zugriff , das Verschieben oder das Löschen eines Werts in einem Array O (1) . Während das lineare Durchsuchen eines Arrays über seinen Index, wie zuvor gesehen, eine Komplexität von O (n) aufweist .

Da eine Verschiebung oder Verschiebung eines Werts zur oder von der Vorderseite eines Arrays die Neuindizierung jedes darauf folgenden Elements erfordert (dh das Entfernen eines Elements am Index 0 erfordert das Umbenennen des Elements am Index 1 als Index 0 usw.), haben sie eine Komplexität von O (n) . Die Neukennzeichnung erfolgt vom Anfang bis zum Ende des Arrays.

Schlüssel-Wert-gepaarte Objekte

Der Zugriff , das Einfügen oder Entfernen eines Werts mithilfe eines Schlüssels erfolgt sofort und hat daher eine Komplexität von O (1) . Das Durchsuchen jedes „Schließfachs“ nach einem bestimmten Artikel unter Verwendung jedes verfügbaren Schlüssels ist im Wesentlichen eine lineare Suche . Und so hat es eine Komplexität von O (n) .

Fazit

Komplexität ist mehr als nur ein Thema für die Diskussion etablierter Algorithmen und Datenstrukturen. Wenn es mit Bedacht eingesetzt wird, kann es ein nützliches Instrument sein, um die Effizienz Ihrer Arbeit und den Code zu messen, den Sie zur Lösung Ihrer Probleme erstellen.

Referenz:

//www.udemy.com/js-algorithms-and-data-structures-masterclass/