So lernen Sie algorithmische Komplexität mit JavaScript

Überblick

In diesem Artikel untersuchen wir, was Begriffe wie „quadratisch“ und „n log(n)“ im Kontext von Algorithmen bedeuten.

In den folgenden Beispielen beziehe ich mich auf diese beiden Arrays, von denen eines 5 Elemente und das andere 50 Elemente enthält. Ich verwende auch die praktische Leistungs-API von JavaScript, um den Unterschied in der Ausführungszeit zu messen.

const smArr = [5, 3, 2, 35, 2];

const bigArr = [5, 3, 2, 35, 2, 5, 3, 2, 35, 2, 5, 3, 2, 35, 2, 5, 3, 2, 35, 2, 5, 3, 2, 35, 2, 5, 3, 2, 35, 2, 5, 3, 2, 35, 2, 5, 3, 2, 35, 2, 5, 3, 2, 35, 2];

Was ist die O-Notation?

Mit der O-Notation lässt sich ausdrücken, dass der allgemeine Schwierigkeitsgrad einer Rechenaufgabe mit zunehmender Größe des Datensatzes zunimmt. Obwohl es auch andere Notationen gibt, wird die O-Notation im Allgemeinen am häufigsten verwendet, da sie sich auf das Worst-Case-Szenario konzentriert, das leichter zu quantifizieren und zu berücksichtigen ist. Der schlimmste Fall ist der, bei dem zur Erledigung der Aufgabe die meisten Handgriffe erforderlich sind. Wenn Sie den Würfel in weniger als einer Sekunde wieder entwirren können, können Sie nicht behaupten, dass Sie die beste Arbeit geleistet hätten, wenn Sie ihn nur einmal gedreht hätten.

Dies ist sehr nützlich, wenn Sie sich tiefer mit Algorithmen befassen, da Sie beim Schreiben von Code diese Beziehung verstehen und wissen, wofür Sie Zeit aufwenden.

Wenn Sie mehr über die O-Notation erfahren, werden Sie möglicherweise verschiedene Variationen des folgenden Diagramms sehen. Wir möchten die Komplexität so gering wie möglich halten und vorzugsweise O(n) nicht überschreiten.

O (1)

Dies ist die ideale Situation. Unabhängig davon, wie viele Projekte es gibt, ob es eins oder eine Million sind, bleibt die bis zur Fertigstellung benötigte Zeit dieselbe. Die meisten Operationen, die eine einzelne Operation ausführen, sind O(1). Das Schreiben von Daten in ein Array, das Abrufen eines Elements an einem bestimmten Index, das Hinzufügen untergeordneter Elemente usw. dauern unabhängig von der Länge des Arrays immer gleich lange.

const a1 = Leistung.jetzt();
smArr.push(27);
const a2 = Leistung.jetzt();
console.log(`Zeit: ${a2 - a1}`); // Weniger als 1 Millisekunde


const b1 = Leistung.jetzt();
großerArr.push(27);
const b2 = Leistung.jetzt();
console.log(`Zeit: ${b2 - b1}`); // Weniger als 1 Millisekunde

An)

Standardmäßig wachsen alle Schleifen linear, da eine Eins-zu-eins-Beziehung zwischen der Datengröße und der bis zur Ausführung benötigten Zeit besteht. Wenn Sie also 1.000 Array-Elemente haben, dauert es 1.000-mal so lange.

const a1 = Leistung.jetzt();
smArr.forEach(Element => console.log(Element));
const a2 = Leistung.jetzt();
console.log(`Zeit: ${a2 - a1}`); // 3 Millisekunden

const b1 = Leistung.jetzt();
bigArr.forEach(Element => console.log(Element));
const b2 = Leistung.jetzt();
console.log(`Zeit: ${b2 - b1}`); // 13 Millisekunden

Ein (n ^ 2)

Exponentielles Wachstum ist eine Falle, in die wir alle tappen. Müssen Sie für jedes Element im Array ein passendes Paar finden? Durch das Einfügen von Schleifen in Schleifen können Sie ein Array aus 1.000 Elementen in eine Million Suchoperationen umwandeln, die dazu führen, dass Ihr Browser nicht mehr reagiert. Es ist besser, 2.000 Operationen in zwei separaten Schleifen auszuführen, als eine Million Operationen in einer doppelt verschachtelten Schleife.

const a1 = Leistung.jetzt();
smArr.forEach(() => {
    arr2.forEach(Element => console.log(Element));
});
const a2 = Leistung.jetzt();
console.log(`Zeit: ${a2 - a1}`); // 8 Millisekunden


const b1 = Leistung.jetzt();
bigArr.fürEach(() => {
    arr2.forEach(Element => console.log(Element));
});
const b2 = Leistung.jetzt();
console.log(`Zeit: ${b2 - b1}`); // 307 Millisekunden

O(log n)

Ich denke, die beste Metapher für logarithmisches Wachstum besteht darin, sich vorzustellen, ein Wort wie „Notation“ im Wörterbuch nachzuschlagen. Sie suchen nicht Begriff für Begriff, sondern finden zuerst den Abschnitt „N“, dann die Seite „OPQ“ und durchsuchen die Liste anschließend alphabetisch, bis Sie eine Übereinstimmung finden.

Bei diesem „Teile und herrsche“-Ansatz hängt die zum Finden eines Ergebnisses benötigte Zeit zwar immer noch von der Größe des Wörterbuchs ab, liegt aber bei weitem nicht bei O(n). Da nach immer spezifischeren Teilen gesucht wird, ohne die gesamte Datenmenge zu betrachten, sind für die Suche nach tausend Elementen möglicherweise weniger als 10 Vorgänge und für die Suche nach einer Million Elementen weniger als 20 Vorgänge erforderlich. So wird Ihre Effizienz maximiert.

In diesem Beispiel können wir eine einfache Schnellsortierung durchführen.

const sort = arr => {
  wenn (arr.length < 2) returniere arr;

  sei pivot = arr[0];
  lass links = [];
  rechts lassen = [];

  für (sei i = 1, gesamt = arr.length; i < gesamt; i++) {
    wenn (arr[i] < pivot) links.drücken(arr[i]);
    sonst right.push(arr[i]);
  };
  zurückkehren [
    ...sortieren(links),
    Drehpunkt,
    ...sortieren (rechts)
  ];
};
sort(smArr); // 0 Millisekunden
sort(bigArr); // 1 Millisekunde

An!)

Die schlimmste Möglichkeit ist faktorielles Wachstum. Das klassische Beispiel ist das Problem des Handlungsreisenden. Wenn Sie zwischen vielen Städten mit unterschiedlicher Entfernung reisen, wie finden Sie die kürzeste Route zwischen allen Städten zurück zu Ihrem Ausgangspunkt? Ein brachialer Ansatz wäre, alle möglichen Streckendistanzen zwischen den einzelnen Städten zu prüfen, was jedoch eine Fakultät ist und schnell außer Kontrolle geraten würde.

Da dieses Problem schnell sehr komplex werden kann, werden wir diese Komplexität anhand einer kurzen rekursiven Funktion demonstrieren. Diese Funktion multipliziert eine Zahl mit sich selbst und subtrahiert dann 1 von der Zahl. Jede Zahl in der Fakultät wird auf diese Weise berechnet, bis sie 0 erreicht, und jede rekursive Ebene addiert ihr Produkt zur ursprünglichen Zahl.

Fakultäten sind einfach die Produkte, die bei 1 beginnen und bis zu dieser Zahl gehen. Dann ist 6! 1x2x3x4x5x6 = 720.

const Fakultät = n => {
  sei num = n;

  wenn (n === 0) return 1
  für (sei i = 0; i < n; i++) {
    Zahl = n * Fakultät(n - 1);
  };

  Rückgabenummer;
};
Fakultät(1); // 2 Millisekunden
Fakultät(5); // 3 Millisekunden
Fakultät(10); // 85 Millisekunden
Fakultät(12); // 11.942 Millisekunden

Ich hatte vorgehabt, Fakultät(15) anzuzeigen, aber Werte über 12 waren zu viel und führten zum Absturz der Seite, was zeigt, warum dies vermieden werden muss.

Abschluss

Dass wir leistungsfähigen Code schreiben müssen, scheint eine unbestreitbare Tatsache zu sein, aber ich bin sicher, dass fast jeder Entwickler mindestens doppelt oder sogar dreifach verschachtelte Schleifen erstellt hat, weil „es einfach funktioniert“. Die O-Notation ist von entscheidender Bedeutung, um Komplexität auf eine Art und Weise auszudrücken und zu betrachten, wie wir es noch nie zuvor getan haben.

Oben finden Sie Einzelheiten zum Erlernen der Algorithmuskomplexität mit JavaScript. Weitere Informationen zur Komplexität von JS-Algorithmen finden Sie in den anderen verwandten Artikeln auf 123WORDPRESS.COM!