Big O Notation ist ein mathematisches Konzept, das verwendet wird, um die Leistung oder Komplexität eines Algorithmus in Bezug auf Zeit und Raum zu beschreiben, wenn die Eingabegröße wächst. Es hilft uns zu verstehen, wie die Laufzeit eines Algorithmus mit größeren Eingaben zunimmt, was einen standardisierten Vergleich verschiedener Algorithmen ermöglicht.

Warum die Big-O-Notation verwenden?

Beim Vergleich von Algorithmen kann es irreführend sein, sich ausschließlich auf die Ausführungszeit zu verlassen. Beispielsweise könnte ein Algorithmus einen riesigen Datensatz in einer Stunde verarbeiten, während ein anderer vier Stunden benötigt. Die Ausführungszeit kann jedoch je nach Maschine und anderen laufenden Prozessen variieren. Stattdessen verwenden wir die Big-O-Notation, um uns auf die Anzahl der durchgeführten Operationen zu konzentrieren, was ein konsistenteres Maß für die Effizienz bietet.

Beispiel: Zahlen summieren

Lassen Sie uns zwei Möglichkeiten erkunden, die Summe aller Zahlen von 1 bis n zu berechnen:

Option 1: Verwendung einer Schleife

function addUpTo(n) {
    let total = 0;
    for (let i = 1; i 




  
  
  Option 2: Verwenden einer Formel




function addUpTo(n) {
    return n * (n   1) / 2;
}





  
  
  Analyse der Komplexität


Wenn in Option 1 n 100 ist, wird die Schleife 100 Mal ausgeführt. Im Gegensatz dazu führt Option 2 immer eine feste Anzahl von Operationen (Multiplikation, Addition und Division) aus. Daher:

• Option 1 ist O(n): Die Zeitkomplexität wächst linear mit n.
• Option 2 ist O(1): Die Zeitkomplexität bleibt unabhängig von der Eingabegröße konstant.

Haftungsausschluss

Während Option 2 drei Operationen umfasst (Multiplikation, Addition, Division), konzentrieren wir uns auf den allgemeinen Trend in der Big-O-Analyse. Anstatt es also als O(3n) auszudrücken, vereinfachen wir es zu O(n). In ähnlicher Weise vereinfacht sich O(n 10) zu O(n) und O(n^2 5n 8) vereinfacht sich zu O(n^2). In der Big-O-Notation betrachten wir das Worst-Case-Szenario, bei dem der Term höchster Ordnung den größten Einfluss auf die Leistung hat.

Es gibt andere Formen der Notation, die über die oben aufgeführten allgemeinen Komplexitäten hinausgehen, wie beispielsweise die logarithmische Zeitkomplexität, ausgedrückt als O(log n).

Was ist die Big-O-Notation?

Mit der Big-O-Notation können wir das Wachstum der Laufzeit eines Algorithmus basierend auf der Eingabegröße formalisieren. Anstatt uns auf bestimmte Operationszahlen zu konzentrieren, kategorisieren wir Algorithmen in breitere Klassen, darunter:

• Konstante Zeit: O(1) – Die Leistung des Algorithmus ändert sich nicht mit der Eingabegröße.
• Lineare Zeit: O(n) – Die Leistung wächst linear mit der Eingabegröße.
• Quadratische Zeit: O(n^2) – Die Leistung wächst quadratisch mit zunehmender Eingabegröße.

Beispiel für O(n^2)

Betrachten Sie die folgende Funktion, die alle Zahlenpaare von 0 bis n ausgibt:

function printAllPairs(n) {
    for (var i = 0; i 



In diesem Fall verfügt die Funktion über zwei verschachtelte Schleifen. Wenn also nnn zunimmt, erhöht sich die Anzahl der Operationen quadratisch. Für n=2 gibt es 4 Operationen und für n=3 gibt es 9 Operationen, die zu O(n^2) führen.


  
  
  Ein weiteres Beispiel: Auf und ab zählen




function countUpAndDown(n) {
    console.log("Going up!");
    for (var i = 0; i = 0; j--) {
        console.log(j);
    }
    console.log("Back down. Bye!");
}





Auf den ersten Blick könnte man denken, dass es sich um O(n^2) handelt, da es zwei Schleifen enthält. Beide Schleifen laufen jedoch unabhängig voneinander und skalieren linear mit n. Somit beträgt die Gesamtzeitkomplexität O(n).


  
  
  Vereinfachung der Analyse


Die Analyse aller Aspekte der Codekomplexität kann komplex sein, aber einige allgemeine Regeln können die Dinge vereinfachen:

• Arithmetische Operationen gelten als konstante Zeit.
• Variablenzuweisungen sind zeitkonstante.
• Der Zugriff auf Elemente in einem Array (nach Index) oder einem Objekt (nach Schlüssel) dauert konstant.
• Für eine Schleife ist die Komplexität die Länge der Schleife multipliziert mit der Komplexität dessen, was innerhalb der Schleife passiert.

Weltraumkomplexität

Während wir uns auf die Zeitkomplexität konzentriert haben, ist es auch möglich, die Raumkomplexität (Speicherkomplexität) mithilfe von Big O zu berechnen. Manche Leute beziehen die Eingabegröße in ihre Berechnungen ein, aber oft ist es sinnvoller, sich ausschließlich auf den vom Algorithmus benötigten Platz zu konzentrieren selbst.

Regeln für Raumkomplexität (basierend auf JavaScript):

• Die meisten primitiven Werte (boolesche Werte, Zahlen usw.) sind konstante Leerzeichen.
• Strings erfordern O(n) Platz (wobei n die Stringlänge ist).
• Referenztypen (Arrays, Objekte) sind im Allgemeinen O(n), wobei n die Länge des Arrays oder die Anzahl der Schlüssel im Objekt ist.

Ein Beispiel

function sum(arr) {
    let total = 0;
    for (let i = ; i 



In dieser Funktion beträgt die Raumkomplexität O(1), da wir unabhängig von der Eingabegröße eine konstante Menge an Raum (zwei Variablen) verwenden.

Für eine Funktion, die ein neues Array erstellt:



function double(arr) {
    let newArr = [];
    for (let i = 0; i 



Hier ist die Platzkomplexität O(n), weil wir Platz für ein neues Array zuweisen, das mit der Größe des Eingabearrays wächst.


  
  
  Abschluss


Big O Notation bietet ein Framework zur Analyse der Effizienz von Algorithmen, unabhängig von Hardware und spezifischen Implementierungsdetails. Das Verständnis dieser Konzepte ist für die Entwicklung effizienten Codes von entscheidender Bedeutung, insbesondere wenn die Datengröße zunimmt. Durch die Konzentration auf die Skalierung der Leistung können Entwickler fundierte Entscheidungen darüber treffen, welche Algorithmen sie in ihren Anwendungen verwenden möchten.