Big-O-Notation verstehen: Ein Leitfaden für Anfänger zur Zeit- und Raumkomplexität

Stellen Sie sich vor, wir haben verschiedene Möglichkeiten, denselben Code zu schreiben. Wie finden wir heraus, welches das Beste ist? Hier kommt die Big-O-Notation ins Spiel. Sie hilft uns zu messen, wie viel Zeit und Platz der Code benötigt, und erleichtert so den Vergleich.

Was ist Big-O-Notation?

Big O, auch bekannt als „Order of“, ist eine Möglichkeit zu beschreiben, wie lange die Ausführung eines Algorithmus im schlimmsten Fall dauern könnte. Es gibt uns eine Vorstellung von der maximalen Zeit, die ein Algorithmus basierend auf der Eingabegröße benötigt. Wir schreiben es als O(f(n)), wobei f(n) angibt, wie viele Schritte der Algorithmus benötigt, um ein Problem mit der Eingabegröße n zu lösen.

Versuchen wir es anhand eines Beispiels zu verstehen „Schreiben Sie eine Funktion, die eine Zeichenfolgeneingabe akzeptiert und eine umgekehrte Kopie zurückgibt“

Okay, ich teile mit Ihnen eine Stack Overflow-Lösung, zusammen mit dem Bild oben, wie Sie sehen können. Es zeigt 10 verschiedene Möglichkeiten zur Lösung desselben Problems, jede mit einem einzigartigen Ansatz.

Die Frage ist nun: Woher wissen wir, welches das Beste ist?

Unser Ziel ist es, die Komplexität von Zeit und Raum zu verstehen. Sehen wir uns dazu ein konkretes Beispiel mit zwei unterschiedlichen Codeausschnitten an, damit wir klar erkennen können, welche Bedeutung diese Konzepte haben.

Hier ist eine Funktion namens addUpTo. Diese Funktion verwendet eine for-Schleife, die läuft, bis sie die Länge von n erreicht und die Gesamtsumme zurückgibt.

Sehen wir uns nun ein weiteres Beispiel an, das die gleiche Funktionalität erreicht:

Welches ist besser?

Was bedeutet nun „besser“ in diesem Zusammenhang wirklich?

• Ist es schneller?

• Benötigt es weniger Speicher?

• Ist es besser lesbar?

Normalerweise konzentrieren sich die Leute auf die ersten beiden – Geschwindigkeit und Speichernutzung – bevor sie sich mit der Lesbarkeit befassen. In diesem Fall konzentrieren wir uns auf die ersten beiden. Um die Leistung beider Codebeispiele zu messen, verwenden wir die integrierten Timing-Funktionen von JavaScript, um ihre Ausführungszeiten zu analysieren und zu vergleichen.

Im obigen Code habe ich t1 und t2 hinzugefügt, die die in JavaScript integrierte Funktion performance.now() nutzen. Mithilfe dieser Funktion können wir die Zeit messen, die der Code zur Ausführung benötigt, und so die Leistung der beiden Ansätze genau vergleichen.

Genau, die Ausführungszeit variiert je nach verschiedenen Faktoren, und das sieht man auch auf meinem Computer – die Zeiten sind nicht konsistent. Die Funktion performance.now() gibt uns keine feste Zeit, liefert aber eine nützliche Schätzung zum Vergleich.

Schauen wir uns nun das zweite Beispiel an:

Beobachten Sie nun den Unterschied in der Ausführungszeit zwischen dem ersten und dem zweiten Codebeispiel. Der zweite ist deutlich schneller als der erste.

Aber was ist das Problem daran, sich ausschließlich auf Zeitmessungen zu verlassen?

• Verschiedene Maschinen zeichnen unterschiedliche Zeiten auf.

• Sogar die gleiche Maschine zeichnet bei jedem Lauf unterschiedliche Zeiten auf.

• Bei sehr schnellen Algorithmen sind Geschwindigkeitsmessungen möglicherweise nicht präzise genug, um einen genauen Vergleich zu ermöglichen.

Diese Faktoren machen zeitbasierte Leistungsbewertungen unzuverlässig, insbesondere für schnelle Algorithmen.

Okay, wenn nicht Zeit, was dann?

Hier hilft uns Big O dabei, sowohl die zeitliche als auch die räumliche Komplexität zu messen. Die Big-O-Notation ist also eine Möglichkeit, das Fuzzy-Zählen zu formalisieren. Es ermöglicht uns, formal darüber zu sprechen, wie die Laufzeit des Algorithmus mit zunehmender Eingabe zunimmt.

Wir sagen, dass ein Algorithmus O(f(n)) ist, wenn die Anzahl der einfachen Operationen, die der Computer ausführen muss, schließlich kleiner als eine Konstante mal f(n) ist, wenn n zunimmt.

• f(n) könnte linear sein (f(n) = n)

• f(n) könnte quadratisch sein (f(n) = n2)

• f(n) könnte konstant sein (f(n) = 1)

• f(n) könnte etwas ganz anderes sein!

Hier ist ein Beispiel:

In diesem Fall haben wir nur 3 Operationen, und unabhängig von der Größe der Eingabe bleiben es immer 3 Operationen. Aus diesem Grund können wir sagen, dass die zeitliche Komplexität dieser Funktion konstant ist, oder O(1).

Hier nun das erste Beispiel:

In diesem Fall nimmt mit zunehmender Eingabe n auch die Anzahl der Operationen proportional zu. Daher hängt die zeitliche Komplexität von der Größe der Eingabe ab, sodass sie O(n) ist.

Sehen wir uns nun ein weiteres Beispiel an:

In diesem Beispiel haben wir zwei verschachtelte for-Schleifen, die beide von n – der Eingabe – abhängig sind. Dies bedeutet, dass mit zunehmender Eingabe n die Anzahl der Operationen erheblich zunimmt. Infolgedessen beträgt die Zeitkomplexität dieses Codes O(n²), auch bekannt als quadratische Zeitkomplexität.

Jetzt vereinfachen wir die Big-O-Notation. Bei der Bestimmung der zeitlichen Komplexität eines Algorithmus sind einige hilfreiche Faustregeln zu beachten. Diese Richtlinien ergeben sich aus der formalen Definition der Big-O-Notation und erleichtern die Analyse von Algorithmen.

Konstanten spielen keine Rolle

• O(2n) = O(n)

• O(500) = O(1)

• O(13n²) = O(n²)

• O(n 10) = O(n)

• O(1000n 500) = O(n)

• O(n² 5n 8) = O(n²)

Big O Kurzschrift

1. Rechenoperationen sind konstant

2. Variablenzuweisung ist konstant

3. Der Zugriff auf Elemente in einem Array (nach Index) oder Objekt (nach Schlüssel) ist konstant

4. In einer Schleife ist die Komplexität die Länge der Schleife multipliziert mit der Komplexität dessen, was innerhalb der Schleife passiert

Hier ist das Big O-Diagramm:

Bisher haben wir aus den Beispielen etwas über O(n) (lineare Zeitkomplexität), O(1) (konstante Zeitkomplexität) und O(n²) (quadratische Zeitkomplexität). Diese decken die Grundmuster ab, bei denen Operationen mit der Eingabegröße wachsen.

Wir werden

O(log n) und O(n log n) – logarithmische und linearithmische Zeitkomplexitäten – etwas später besprechen.

Weltraumkomplexität

Bisher haben wir uns auf die zeitliche Komplexität konzentriert: Wie können wir die Laufzeit eines Algorithmus analysieren, wenn die Größe der Eingaben zunimmt?

Wir können auch die Big-O-Notation verwenden, um die Raumkomplexität zu analysieren: Wie viel zusätzlichen Speicher müssen wir zuweisen, um den Code in unserem Algorithmus auszuführen?

Was ist mit den Eingaben?

Manchmal hört man den Begriff „Hilfsraumkomplexität“, um sich auf den vom Algorithmus benötigten Platz zu beziehen, nicht einschließlich des durch die Eingaben belegten Platzes. Sofern nicht anders angegeben, sprechen wir, wenn wir über Raumkomplexität sprechen, technisch gesehen über Hilfsraumkomplexität.

Raumkomplexität in JS

• Die meisten Grundelemente (boolesche Werte, Zahlen, undefiniert, null) sind konstante Leerzeichen

• Strings erfordern O(n) Speicherplatz (wobei n die Stringlänge ist). Referenztypen sind im Allgemeinen O(n), wobei n die Länge (für Arrays) oder die Anzahl der Schlüssel (für Objekte) ist

Denken Sie daran, wir sprechen von räumlicher Komplexität, nicht von zeitlicher Komplexität. In diesem Code können wir sehen, dass wir nur zwei Variablen haben. Unabhängig davon, wie groß die Eingabe wird, sind diese beiden Variablen immer im Code vorhanden. Da wir mit zunehmender Eingabe keine neuen Variablen hinzufügen, können wir sagen, dass die Raumkomplexität O(1) ist, was bedeutet, dass es sich um eine konstante Raumkomplexität handelt.

Verstehen wir es anhand eines anderen Beispiels:

In diesem Code gibt die Funktion newArr zurück, nachdem jedes Element im Eingabearray verdoppelt wurde. Da die Größe von newArr direkt proportional zur Größe des Eingabe-Arr ist, wächst der von newArr verwendete Speicherplatz mit der Eingabegröße. Im Gegensatz zum vorherigen Beispiel, bei dem der Speicherplatz konstant war, hängt die Speicherplatzkomplexität hier von der Größe des Eingabearrays ab. Daher ist die Raumkomplexität O(n), was bedeutet, dass sie linear ist.

Ich hoffe, dass dies die Raumkomplexität klarer macht – genau wie die Zeitkomplexität messen wir sie mithilfe der Big-O-Notation. Bisher haben Sie verschiedene Zeitkomplexitäten in aufsteigender Reihenfolge der Komplexität kennengelernt: O(1), O(log n), O(n), O(n log n), O(n²), O(n³) und so weiter. Allerdings haben wir die logarithmische Zeitkomplexität noch nicht untersucht.

Als nächstes tauchen wir in die logarithmische Zeitkomplexität ein und sehen, wie es funktioniert.

Logarithmen

Wir sind auf einige der häufigsten Komplexitäten gestoßen: O(1), O(n), O(n2). Manchmal beinhalten große O-Ausdrücke komplexere mathematische Ausdrücke. Einer, der häufiger vorkommt, als Ihnen vielleicht lieb ist, ist der Logarithmus!

Was ist nochmal ein Protokoll?

log2 (8) = 3 → 2³ = 8

log2 (Wert) = Exponent → 2^Exponent = Wert

Wir lassen die 2 weg, was bedeutet:

log === log2

Der Logarithmus einer Zahl misst grob, wie oft Sie diese Zahl durch 2 teilen können, bevor sie kleiner oder gleich 1 wird. Dies macht logarithmische Zeitkomplexität sehr effizient. Wie Sie im Diagramm gesehen haben, liegt O(1) (konstante Zeit) sehr nahe an O(log n), was fantastisch ist! Es ist auch erwähnenswert, dass O(n log n) hinsichtlich der Effizienz viel besser ist als O(n²), was es zu einer bevorzugten Komplexität für viele Algorithmen macht.

• Bestimmte Suchalgorithmen haben eine logarithmische Zeitkomplexität.

• Effiziente Sortieralgorithmen beinhalten Logarithmen.

• Rekursion beinhaltet manchmal logarithmische Raumkomplexität.

Großartig! Wir haben die meisten wichtigen Punkte zur räumlichen und zeitlichen Komplexität behandelt. Denken Sie daran, dass das Beherrschen dieser Konzepte Übung erfordert. Fühlen Sie sich also nicht überfordert, wenn es nicht sofort völlig klar ist. Nehmen Sie sich Zeit, gehen Sie das Material mehrmals durch und schauen Sie sich bei Bedarf noch einmal Beispiele an. Es dauert oft ein paar Wiederholungen, bis diese Ideen wirklich greifen, also haben Sie Geduld mit sich selbst!

Lassen Sie uns zum Schluss noch einmal zusammenfassen:

• Um die Leistung eines Algorithmus zu analysieren, verwenden wir die Big-O-Notation

• Die Big-O-Notation kann uns ein umfassendes Verständnis der zeitlichen oder räumlichen Komplexität eines Algorithmus vermitteln

• Big O Notation kümmert sich nicht um Präzision, sondern nur um allgemeine Trends (linear? quadratisch? konstant?)

Auch hier ist die Big-O-Notation überall, also üben Sie viel!

---

Wir bei CreoWis glauben daran, Wissen öffentlich zu teilen, um das Wachstum der Entwicklergemeinschaft zu unterstützen. Lassen Sie uns zusammenarbeiten, Ideen entwickeln und Leidenschaft entwickeln, um der Welt beeindruckende Produkterlebnisse zu bieten.

Vernetzen wir uns:

• X/Twitter

• LinkedIn

• Website

Dieser Artikel wurde von Syket Bhattachergee verfasst, einem leidenschaftlichen Entwickler bei CreoWis. Sie können ihn auf X/Twitter, LinkedIn erreichen und seine Arbeit auf dem GitHub verfolgen.

Das obige ist der detaillierte Inhalt vonBig-O-Notation verstehen: Ein Leitfaden für Anfänger zur Zeit- und Raumkomplexität. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!