Leitfaden für Anfänger zur Big O-Notation

Die Big O-Notation gibt an, wie lange die Ausführung eines Algorithmus dauern wird. Es ermöglicht einem Software-Ingenieur zu bestimmen, wie effizient verschiedene Ansätze zur Lösung eines Problems sind.

Hier sind einige gängige Arten von Zeitkomplexitäten in der Big O-Notation.

  • O (1) - Konstante zeitliche Komplexität
  • O (n) - Lineare Zeitkomplexität
  • O (log n) - Logarithmische Zeitkomplexität
  • O (n ^ 2) - Quadratische Zeitkomplexität

Hoffentlich können Sie am Ende dieses Artikels die Grundlagen der Big O-Notation verstehen.

O (1) - Konstante Zeit

Konstante Zeitalgorithmen benötigen immer dieselbe Zeit für die Ausführung. Die Ausführungszeit dieses Algorithmus ist unabhängig von der Größe der Eingabe. Ein gutes Beispiel für O (1) -Zeit ist der Zugriff auf einen Wert mit einem Array-Index.

var arr = [ 1,2,3,4,5];
arr[2]; // => 3

Andere Beispiele sind: push () - und pop () -Operationen für ein Array.

O (n) - Lineare Zeitkomplexität

Ein Algorithmus hat eine lineare Zeitkomplexität, wenn die Zeit zum Ausführen des Algorithmus direkt proportional zur Eingabegröße n ist . Daher nimmt die Zeit, die zum Ausführen des Algorithmus benötigt wird, proportional zu, wenn die Größe der Eingabe n zunimmt.

Ein gutes Beispiel ist das Auffinden einer CD in einem CD-Stapel oder das Lesen eines Buches, wobei n die Anzahl der Seiten ist.

Beispiele in O (n) verwenden die lineare Suche:

//if we used for loop to print out the values of the arrays
for (var i = 0; i < array.length; i++) { console.log(array[i]);}
var arr1 = [orange, apple, banana, lemon]; //=> 4 steps
var arr2 = [apple, htc,samsung, sony, motorola]; //=> 5 steps

O (log n) - Logarithmische Zeitkomplexität

Ein Algorithmus hat eine logarithmische Zeitkomplexität, wenn die Zeit, die zum Ausführen des Algorithmus benötigt wird, proportional zum Logarithmus der Eingabegröße n ist . Ein Beispiel ist die binäre Suche, die häufig zum Durchsuchen von Datensätzen verwendet wird:

//Binary search implementationvar doSearch = function(array, targetValue) { var minIndex = 0; var maxIndex = array.length - 1; var currentIndex; var currentElement; while (minIndex <= maxIndex) { currentIndex = (minIndex + maxIndex) / 2 | 0; currentElement = array[currentIndex]; if (currentElement  targetValue) { maxIndex = currentIndex - 1; } else { return currentIndex; } } return -1; //If the index of the element is not found.};
var numbers = [11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33];
doSearch(numbers, 23) //=>; 6

Andere Beispiele für logarithmische Zeitkomplexität sind:

Example 1;
for (var i = 1; i < n; i = i * 2) console.log(i);}
Example 2;
for (i = n; i >= 1; i = i/2) console.log(i);}

O (n ^ 2) - Quadratische Zeitkomplexität

Ein Algorithmus hat eine quadratische Zeitkomplexität, wenn die Zeit bis zur Ausführung proportional zum Quadrat der Eingabegröße ist. Ein gutes Beispiel hierfür ist die Überprüfung, ob ein Kartenspiel Duplikate enthält.

Bei Algorithmen mit verschachtelten Iterationen, z. B. verschachtelten for-Schleifen, tritt eine quadratische Zeitkomplexität auf . Tatsächlich führen die tieferen verschachtelten Schleifen zu O (n ^ 3), O (n ^ 4) usw.

for(var i = 0; i < length; i++) { //has O(n) time complexity for(var j = 0; j < length; j++) { //has O(n^2) time complexity // More loops? }}

Andere Beispiele für quadratische Zeitkomplexität umfassen Blasensortierung, Auswahlsortierung und Einfügesortierung.

Dieser Artikel kratzt nur die Oberfläche der Big O-Notation. Wenn Sie mehr über die Big O-Notation erfahren möchten, empfehlen wir Ihnen, das Big-O-Spickzettel zu lesen.