Datenstrukturen - Asymptotische Analyse

Die asymptotische Analyse eines Algorithmus bezieht sich auf die Definition der mathematischen Grenze / des Rahmens seiner Laufzeitleistung. Mit Hilfe der asymptotischen Analyse können wir sehr gut den besten Fall, den durchschnittlichen Fall und das schlechteste Szenario eines Algorithmus schließen.

Die asymptotische Analyse ist eingabegebunden, dh wenn keine Eingabe in den Algorithmus erfolgt, wird davon ausgegangen, dass sie in einer konstanten Zeit funktioniert. Mit Ausnahme der "Eingabe" werden alle anderen Faktoren als konstant betrachtet.

Die asymptotische Analyse bezieht sich auf die Berechnung der Laufzeit einer Operation in mathematischen Recheneinheiten. Beispielsweise wird die Laufzeit einer Operation als f (n) berechnet und kann für eine andere Operation als g (n ² ) berechnet werden . Dies bedeutet, dass die Laufzeit des ersten Vorgangs linear mit der Zunahme von zunimmtn und die Laufzeit der zweiten Operation wird exponentiell ansteigen, wenn nerhöht sich. In ähnlicher Weise ist die Laufzeit beider Operationen nahezu gleich, wennn ist deutlich klein.

Normalerweise fällt die von einem Algorithmus benötigte Zeit unter drei Typen:

Best Case - Mindestzeit für die Programmausführung.
Average Case - Durchschnittliche Zeit für die Programmausführung.
Worst Case - Maximale Zeit für die Programmausführung.

Asymptotische Notationen

Im Folgenden sind die häufig verwendeten asymptotischen Notationen aufgeführt, um die Laufzeitkomplexität eines Algorithmus zu berechnen.

Ο Notation
Ω Notation
θ Notation

Big Oh Notation, Ο

Die Notation Ο (n) ist der formale Weg, um die Obergrenze der Laufzeit eines Algorithmus auszudrücken. Es misst die Zeitkomplexität im ungünstigsten Fall oder die längste Zeit, die ein Algorithmus möglicherweise in Anspruch nehmen kann.

Zum Beispiel für eine Funktion f(n)

Ο(f(n)) = { g(n) : there exists c > 0 and n₀ such that f(n) ≤ c.g(n) for all n > n₀. }

Omega-Notation, Ω

Die Notation Ω (n) ist der formale Weg, um die Untergrenze der Laufzeit eines Algorithmus auszudrücken. Es misst die beste Zeitkomplexität oder die beste Zeit, die ein Algorithmus möglicherweise für die Fertigstellung benötigt.

Zum Beispiel für eine Funktion f(n)

Ω(f(n)) ≥ { g(n) : there exists c > 0 and n₀ such that g(n) ≤ c.f(n) for all n > n₀. }

Theta-Notation, θ

Die Notation θ (n) ist der formale Weg, um sowohl die Untergrenze als auch die Obergrenze der Laufzeit eines Algorithmus auszudrücken. Es wird wie folgt dargestellt:

θ(f(n)) = { g(n) if and only if g(n) =  Ο(f(n)) and g(n) = Ω(f(n)) for all n > n₀. }

Häufige asymptotische Notationen

Es folgt eine Liste einiger gebräuchlicher asymptotischer Notationen -

Konstante	- -	Ο (1)
logarithmisch	- -	Ο (log n)
linear	- -	Ο (n)
n log n	- -	Ο (n log n)
quadratisch	- -	Ο (n ² )
kubisch	- -	Ο (n ³ )
Polynom	- -	n ^{Ο (1)}
exponentiell	- -	2 ^{Ο (n)}