Big-o-Notation in der Datenstruktur: Alles zu wissen

Die Big-O-Notation in einer Datenstruktur wird verwendet, um die Effizienz eines Algorithmus, die Zeit, die zum Ausführen der Funktion mit dem Wachstum der Eingabe benötigt wird, und die Skalierung der Funktion zu bestimmen. Die Messung dieser Effizienz kann in zwei Teile unterteilt werden, nämlich Raumkomplexität und Zeitkomplexität.

Die Big-O-Notation bezieht sich auf die mathematische Notation, die als begrenzender Faktor jeder Funktion fungiert, wenn ein Argument eher zu einem bestimmten Wert oder unendlich tendiert. Es gehört zur Kategorie der mathematischen Notationen, die von Edmund Landau, Paul Bachmann und anderen erfunden wurden. Daher wird es zusammenfassend als Bachmann-Landau-Notation oder asymptotische Notation bezeichnet.

Gemäß der mathematischen Ableitung werden zwei Funktionen, f(n) und g(n) , auf einer Menge positiver oder reeller Zahlen definiert, die nicht gebunden sind. Dabei ist g(n) für jeden großen Wert von n streng positiv. Es kann auf folgende Weise geschrieben werden:

f(n) = O(g(n)) wobei n gegen unendlich geht (n → ∞)

Hier ist jedoch die Annahme von n bis unendlich nicht ausschließlich definiert, und der obige Ausdruck kann daher geschrieben werden als:

f(n) = O(g(n))

Hier sind f und g die notwendigen Funktionen, die von positiven ganzen Zahlen bis zu reellen Zahlen reichen, die nicht negativ sind.

Daher werden große n-Werte durch die Big-O-Asymptotik bezeichnet.

Eigenschaften der Big-O-Notation in der Datenstruktur

Der Big O -Algorithmus in der Datenstruktur hat einige zwingend erforderliche Eigenschaften. Die besagten wesentlichen Eigenschaften der Big-O-Notation sind wie folgt:

• Summenfunktion:
  Wenn f(n) = f 1 (n) + f 2 (n) + — + f m (n) und f i (n)≤ f i +1(n) ∀ i=1, 2,–, m,
  dann O(f(n)) = O(max(f1(n), f2(n), –, fm(n))).
• Logarithmische Funktion:
  Wenn f(n) = logan und g(n)=logbn,
  dann O(f(n))=O(g(n))
• Konstante Multiplikation:
  Wenn f(n) = cg(n), dann O(f(n)) = O(g(n)), wobei c eine Konstante ungleich Null ist.
• Polynomfunktion:
  Wenn f(n) = a0 + a1.n + a2.n2 + — + am.nm,
  dann O(f(n)) = O(nm).

Lernen Sie Softwareentwicklungskurse online von den besten Universitäten der Welt. Verdienen Sie Executive PG-Programme, Advanced Certificate-Programme oder Master-Programme, um Ihre Karriere zu beschleunigen.

Erkunden Sie unsere beliebten Softwareentwicklungskurse

Während hier Big O angesprochen wird, erhöht sich jede einzelne Protokollfunktion ähnlich.

Bedeutung der großen O-Notation bei der Laufzeitanalyse von Algorithmen

Die Komplexitäten der Worst-Case-Laufzeit des Algorithmus werden verwendet, um Vergleiche zu ziehen und zu berechnen, insbesondere im Fall der Analyse der Leistung eines Algorithmus. Die Ordnung O(1), dargestellt als konstante Laufzeit, ist die schnellste Laufzeit des Algorithmus – die Zeit, die der Algorithmus benötigt, ist für verschiedene Eingabegrößen gleich. Es ist wichtig zu beachten, dass die ideale Laufzeit eines Algorithmus die konstante Laufzeit ist, die sehr selten erreicht wird, da die Laufzeit des Algorithmus von der Eingabegröße von n abhängt.

Zum Beispiel:

Wie oben erwähnt, hängt die Laufzeitleistung eines Algorithmus hauptsächlich von der Eingabegröße von n ab. Verdeutlichen wir uns diesen Sachverhalt an einigen mathematischen Beispielen, um die Laufzeitanalyse eines Algorithmus für verschiedene Größen von n zu machen:

• n = 20
  log (20) = 2,996;
  20 = 20;
  20 log (20) = 59,9;
  20 2 = 400;
  2 20 = 1084576;
  20! = 2,432902 + 18 18 ;
• n = 10
  Protokoll (10) = 1;
  10 = 10;
  10 log (10) = 10;
  10 2 = 100;
  2 10 = 1024;
  10! = 3628800;

Die Laufzeitleistung eines Algorithmus wird ähnlich berechnet.

Hier sind ein paar andere algorithmische Beispiele für die Laufzeitanalyse –

• Bei der linearen Suche beträgt die Laufzeitkomplexität O(n).
• Die Laufzeitkomplexität beträgt O(log n) für die binäre Suche.
• Für Selection Sort, Bubble Sort, Bucket Sort, Insertion Sort beträgt die Laufzeitkomplexität O(n^c).
• Bei exponentiellen Algorithmen wie Tower of Hanoi beträgt die Laufzeitkomplexität O(c^n).
• Für Merge SortSort und Heap Sort beträgt die Laufzeitkomplexität O(n log n).

Wie analysiert Big O die Raumkomplexität?

Die Bestimmung sowohl des Speicherplatzes als auch der Laufzeitkomplexität für einen Algorithmus ist ein wesentlicher Schritt. Dies liegt daran, dass wir die Ausführungszeit, die ein Algorithmus benötigt, bestimmen können, indem wir die Laufzeitleistung des Algorithmus und den Speicherplatz, den der Algorithmus einnimmt, durch die Analyse der Speicherplatzkomplexität des Algorithmus analysieren. Um die Raumkomplexität eines Algorithmus zu messen, müssen wir daher die Raumkomplexitätsleistung des Algorithmus im schlimmsten Fall vergleichen.

Um die Raumkomplexität eines Algorithmus zu bestimmen, müssen wir diesen beiden Aufgaben nachgehen –

Aufgabe 1: Es ist wichtig, das Programm für einen bestimmten Algorithmus zu implementieren.

Aufgabe 2: Es ist wichtig, die Größe der Eingabe n zu kennen, um den Speicher zu bestimmen, den jedes Element haben wird.

Diese beiden wesentlichen Aufgaben müssen erfüllt werden, bevor die Raumkomplexität für einen Algorithmus berechnet wird.

Beispiele für Raumkomplexitätsalgorithmen

Es gibt viele Beispiele für Algorithmen mit Raumkomplexität, von denen einige unten zum besseren Verständnis dieser Art von Algorithmus erwähnt wurden:

• Für Blasensortierung, lineare Suche, Auswahlsortierung, Einfügungssortierung, Heapsortierung und binäre Suche beträgt die Raumkomplexität O(1) .
• Die Raumkomplexität ist O(n+k), wenn es um Radixsort geht .
• Die Platzkomplexität ist O(n) für schnelles SortSort.
• Die Raumkomplexität ist O(log n) für Mischsortierung.

Beispiel für Big-O-Notation in C

Es ist eine Tatsache, dass die Big-O-Notation hauptsächlich in der Informatik verwendet wird, um die Komplexität oder Leistung eines Algorithmus zu bestimmen. Diese Notation bietet uns die Möglichkeit, das Verhalten von Algorithmen basierend auf dem Wachstum des Speicherplatzes oder der Anforderungen an die Ausführungszeit zu klassifizieren, wenn der Umfang der Eingabedaten groß wird. Es ist nicht darauf ausgelegt, die tatsächliche Speichernutzung oder Ausführungszeit vorherzusagen, sondern Algorithmen zu vergleichen und dann die besten für den Job auszuwählen. Es ist nicht sprachspezifisch, sondern auch in C implementiert.

Unten finden Sie den Auswahlsortieralgorithmus in C, wo die Worst-Case-Komplexität (Big-O-Notation) des Algorithmus berechnet wurde:-

for(int i=0; i<n; i++)

{

intmin = ich;

for(int j=i; j<n; j++)

{

if(Array[j]<Array[min])

min=j;

}

int temp = array[i];

Array[i] = Array[min];

array[min] = temp;

}

So analysieren Sie den Algorithmus:

• Es kann bereits angemerkt werden, dass der Bereich der äußeren for-Schleife i < n ist, was besagt, dass die Ordnung der Schleife O(n) ist.
• Als nächstes können wir erkennen, dass es auch O(n) ist, da j < n für die innere for-Schleife.
• Die Konstante wird ignoriert, selbst wenn die mittlere Effizienz n/2 für eine Konstante c gefunden wird. Also ist die Reihenfolge O(n).
• Nach der Multiplikation der Reihenfolge der inneren Schleife und der äußeren Schleife beträgt die erreichte Laufzeitkomplexität O(n^2).

Andere Algorithmen in C können leicht implementiert werden, wobei die Komplexitäten leicht analysiert und ähnlich bestimmt werden können.

Verwendung der großen O-Notation

Es gibt zwei Hauptbereiche, in denen die Big-O-Notation angewendet wird:-

• Mathematik : Die Big O-Notation wird im Bereich der Mathematik häufig verwendet, um zu beschreiben, wie eine endliche Reihe eine Funktion genau annähert, insbesondere wenn es um Fälle einer asymptotischen Entwicklung oder abgeschnittener Taylor-Reihen geht.
• Informatik: Es ist eine allgemein anerkannte Tatsache, dass die Big-O-Notation aufgrund ihrer Nützlichkeit bei der Analyse von Algorithmen hauptsächlich im Bereich der Informatik verwendet wird

Jedoch wird in beiden Anwendungen die Funktion g ( x ), die innerhalb des O (·) erscheint, oft so gewählt, dass sie möglicherweise die einfachste ist, wenn Terme niedrigerer Ordnung und konstante Faktoren weggelassen werden.

Es gibt zwei andere Verwendungen dieser Notation, die formal ähnlich, aber relativ unterschiedlich sind. Sie sind:-

• Unendliche Asymptotik
• Infinitesimale Asymptotik.

Diese Unterscheidung ist jedoch nicht grundsätzlich, sondern nur dann anwendbar, wenn die formale Definition für das „Big O“ für beide Fälle exakt gleich ist. Der einzige Unterschied sind die Grenzen für das Argument der Funktion.

Lesen Sie unsere beliebten Artikel zur Softwareentwicklung

Fazit

Zusammenfassend können wir sagen, dass Big Data eine integrale Rolle in Datenstrukturen spielt, und dass ein fundiertes, umfassendes Wissen über die Big O-Notation eine hervorragende Fähigkeit ist, über die man verfügen sollte. Es ist in der Arbeitswelt sehr gefragt und kann möglicherweise eine gute Wahl für einen Karriereweg sein. Das Advanced Certificate Program in Big Data von upGrad gibt Ihnen den nötigen Hebel, um Ihre Karriere anzukurbeln. Es führt Sie in professionelle Top-Fähigkeiten wie Datenverarbeitung mit PySpark, Data Warehousing, MapReduce, Big Data-Verarbeitung in der AWS Cloud, Echtzeitverarbeitung usw. ein.