In diesem Tutorial lernen Sie, was asymptotische Notationen sind. Außerdem lernen Sie die Big-O-Notation, die Theta-Notation und die Omega-Notation kennen.
Die Effizienz eines Algorithmus hängt von der Zeit, dem Speicher und anderen Ressourcen ab, die zur Ausführung des Algorithmus erforderlich sind. Die Effizienz wird mit Hilfe von asymptotischen Notationen gemessen.
Ein Algorithmus hat möglicherweise nicht die gleiche Leistung für verschiedene Arten von Eingaben. Mit zunehmender Eingangsgröße ändert sich die Leistung.
Die Untersuchung der Änderung der Leistung des Algorithmus mit der Änderung der Reihenfolge der Eingabegröße wird als asymptotische Analyse definiert.
Asymptotische Notationen
Asymptotische Notationen sind die mathematischen Notationen, die zur Beschreibung der Laufzeit eines Algorithmus verwendet werden, wenn die Eingabe zu einem bestimmten Wert oder einem Grenzwert tendiert.
Beispiel: Wenn beim Blasensortieren das Eingabearray bereits sortiert ist, ist die vom Algorithmus benötigte Zeit linear, dh der beste Fall.
Wenn sich das Eingabearray jedoch in einem umgekehrten Zustand befindet, benötigt der Algorithmus die maximale Zeit (quadratisch), um die Elemente zu sortieren, dh im schlimmsten Fall.
Wenn das Eingabearray weder sortiert noch in umgekehrter Reihenfolge ist, dauert es durchschnittlich lange. Diese Dauern werden mit asymptotischen Notationen bezeichnet.
Es gibt hauptsächlich drei asymptotische Notationen:
- Big-O-Notation
- Omega-Notation
- Theta-Notation
Big-O-Notation (O-Notation)
Die Big-O-Notation repräsentiert die Obergrenze der Laufzeit eines Algorithmus. Somit ergibt sich die Worst-Case-Komplexität eines Algorithmus.
Big-O gibt die Obergrenze einer Funktion an
O (g (n)) = (f (n): es existieren positive Konstanten c und n 0, so dass 0 ≤ f (n) ≤ cg (n) für alle n ≤ n 0 )
Der obige Ausdruck kann als eine Funktion beschrieben werden f(n), die zur Menge gehört, O(g(n))wenn eine positive Konstante existiert, cso dass sie zwischen 0und cg(n)für ausreichend groß liegt n.
Für jeden Wert von nüberschreitet die Laufzeit eines Algorithmus nicht die von bereitgestellte Zeit O(g(n)).
Da es die Worst-Case-Laufzeit eines Algorithmus angibt, wird es häufig zur Analyse eines Algorithmus verwendet, da wir immer am Worst-Case-Szenario interessiert sind.
Omega-Notation (Ω-Notation)
Die Omega-Notation repräsentiert die Untergrenze der Laufzeit eines Algorithmus. Somit bietet es die beste Komplexität eines Algorithmus.
Omega gibt die Untergrenze einer Funktion an
Ω (g (n)) = (f (n): es existieren positive Konstanten c und n 0, so dass 0 ≦ cg (n) ≦ f (n) für alle n ≧ n 0 )
Der obige Ausdruck kann als eine Funktion beschrieben werden f(n), die zur Menge gehört, Ω(g(n))wenn eine positive Konstante existiert, cso dass sie cg(n)für ausreichend groß darüber liegt n.
Für jeden Wert von nwird die vom Algorithmus benötigte Mindestzeit von Omega angegeben Ω(g(n)).
Theta-Notation (Θ-Notation)
Die Theta-Notation umschließt die Funktion von oben und unten. Da es die Ober- und Untergrenze der Laufzeit eines Algorithmus darstellt, wird es zur Analyse der Durchschnittskomplexität eines Algorithmus verwendet.
Theta begrenzt die Funktion innerhalb von Konstantenfaktoren
Für eine Funktion g(n), Θ(g(n))durch die Beziehung gegeben:
Θ (g (n)) = (f (n): Es existieren positive Konstanten c 1 , c 2 und n 0, so dass 0 ≦ c 1 g (n) ≦ f (n) ≦ c 2 g (n) für alle n ≧ n 0 )
Der obige Ausdruck kann als eine Funktion beschrieben werden f(n), die zur Menge gehört, Θ(g(n))wenn positive Konstanten existieren und so, dass er zwischen und für ausreichend großes n angeordnet werden kann.c1c2c1g(n)c2g(n)
Liegt eine Funktion f(n)irgendwo dazwischen und für alle , so spricht man von einer asymptotisch engen Bindung.c1g(n)c2g(n)n ≧ n0f(n)
