Asymptotische Notationen und Apriori-Analyse
Beim Entwurf eines Algorithmus ist die Komplexitätsanalyse eines Algorithmus ein wesentlicher Aspekt. Die algorithmische Komplexität hängt hauptsächlich von der Leistung ab, davon, wie schnell oder langsam sie funktioniert.
Die Komplexität eines Algorithmus beschreibt die Effizienz des Algorithmus in Bezug auf die zur Verarbeitung der Daten erforderliche Speichermenge und die Verarbeitungszeit.
Die Komplexität eines Algorithmus wird aus zwei Perspektiven analysiert: Time und Space.
Zeitliche Komplexität
Diese Funktion beschreibt die zum Ausführen eines Algorithmus erforderliche Zeit in Bezug auf die Größe der Eingabe. "Zeit" kann die Anzahl der durchgeführten Speicherzugriffe, die Anzahl der Vergleiche zwischen ganzen Zahlen, die Häufigkeit der Ausführung einer inneren Schleife oder eine andere natürliche Einheit in Bezug auf die Echtzeitdauer des Algorithmus bedeuten.
Raumkomplexität
Diese Funktion beschreibt die Speichermenge, die ein Algorithmus in Bezug auf die Größe der Eingabe in den Algorithmus benötigt. Wir sprechen oft von "zusätzlichem" Speicher, der benötigt wird, ohne den Speicher zu zählen, der zum Speichern der Eingabe selbst benötigt wird. Auch hier verwenden wir natürliche Einheiten (mit fester Länge), um dies zu messen.
Die Komplexität des Raums wird manchmal ignoriert, da der verwendete Platz minimal und / oder offensichtlich ist. Manchmal wird er jedoch genauso wichtig wie die Zeit.
Asymptotische Notationen
Die Ausführungszeit eines Algorithmus hängt vom Befehlssatz, der Prozessorgeschwindigkeit, der Platten-E / A-Geschwindigkeit usw. ab. Daher schätzen wir die Effizienz eines Algorithmus asymptotisch.
Die Zeitfunktion eines Algorithmus wird durch dargestellt T(n), wo n ist die Eingabegröße.
Verschiedene Arten von asymptotischen Notationen werden verwendet, um die Komplexität eines Algorithmus darzustellen. Die folgenden asymptotischen Notationen werden verwendet, um die Laufzeitkomplexität eines Algorithmus zu berechnen.
O - Großes Oh
Ω - Großes Omega
θ - Großes Theta
o - Wenig Oh
ω - Kleines Omega
O: Asymptotische Obergrenze
'O' (Big Oh) ist die am häufigsten verwendete Notation. Eine Funktionf(n) dargestellt werden kann, ist die Reihenfolge von g(n) das ist O(g(n)), wenn ein Wert von positiver Ganzzahl vorhanden ist n wie n0 und eine positive Konstante c so dass -
$ f (n) \ leqslant cg (n) $ für $ n> n_ {0} $ in jedem Fall
Daher Funktion g(n) ist eine Obergrenze für die Funktion f(n), wie g(n) wächst schneller als f(n).
Beispiel
Betrachten wir eine gegebene Funktion, $ f (n) = 4.n ^ 3 + 10.n ^ 2 + 5.n + 1 $
Betrachtet man $ g (n) = n ^ 3 $,
$ f (n) \ leqslant 5.g (n) $ für alle Werte von $ n> 2 $
Daher die Komplexität von f(n) kann als $ O (g (n)) $ dargestellt werden, dh $ O (n ^ 3) $
Ω: Asymptotische Untergrenze
Wir sagen, dass $ f (n) = \ Omega (g (n)) $ ist, wenn es eine Konstante gibt c dass $ f (n) \ geqslant cg (n) $ für alle ausreichend großen Werte von n. Hiernist eine positive ganze Zahl. Es bedeutet Funktiong ist eine Untergrenze für die Funktion f;; nach einem bestimmten Wert vonn, f wird niemals untergehen g.
Beispiel
Betrachten wir eine gegebene Funktion, $ f (n) = 4.n ^ 3 + 10.n ^ 2 + 5.n + 1 $.
Unter Berücksichtigung von $ g (n) = n ^ 3 $ gilt $ f (n) \ geqslant 4.g (n) $ für alle Werte von $ n> 0 $.
Daher die Komplexität von f(n) kann als $ \ Omega (g (n)) $ dargestellt werden, dh $ \ Omega (n ^ 3) $
θ: Asymptotisch eng gebunden
Wir sagen, dass $ f (n) = \ theta (g (n)) $ ist, wenn Konstanten existieren c1 und c2 dass $ c_ {1} .g (n) \ leqslant f (n) \ leqslant c_ {2} .g (n) $ für alle ausreichend großen Werte von n. Hiern ist eine positive ganze Zahl.
Das bedeutet Funktion g ist eine enge Funktion f.
Beispiel
Betrachten wir eine gegebene Funktion, $ f (n) = 4.n ^ 3 + 10.n ^ 2 + 5.n + 1 $
Unter Berücksichtigung von $ g (n) = n ^ 3 $, $ 4.g (n) \ leqslant f (n) \ leqslant 5.g (n) $ für alle großen Werte von n.
Daher die Komplexität von f(n) kann als $ \ theta (g (n)) $ dargestellt werden, dh $ \ theta (n ^ 3) $.
O - Notation
Die asymptotische Obergrenze von O-notationkann asymptotisch eng sein oder nicht. Die Grenze $ 2.n ^ 2 = O (n ^ 2) $ ist asymptotisch eng, die Grenze $ 2.n = O (n ^ 2) $ jedoch nicht.
Wir gebrauchen o-notation eine Obergrenze zu bezeichnen, die nicht asymptotisch eng ist.
Wir definieren formal o(g(n)) (little-oh von g von n) als Menge f(n) = o(g(n)) für jede positive Konstante $ c> 0 $ existiert ein Wert $ n_ {0}> 0 $, so dass $ 0 \ leqslant f (n) \ leqslant cg (n) $.
Intuitiv in der o-notation, die Funktion f(n) wird relativ zu unbedeutend g(n) wie nnähert sich der Unendlichkeit; das ist,
$$ \ lim_ {n \ rightarrow \ infty} \ left (\ frac {f (n)} {g (n)} \ right) = 0 $$
Beispiel
Betrachten wir dieselbe Funktion: $ f (n) = 4.n ^ 3 + 10.n ^ 2 + 5.n + 1 $
Betrachtet man $ g (n) = n ^ {4} $,
$$ \ lim_ {n \ rightarrow \ infty} \ left (\ frac {4.n ^ 3 + 10.n ^ 2 + 5.n + 1} {n ^ 4} \ right) = 0 $$
Daher die Komplexität von f(n) kann als $ o (g (n)) $ dargestellt werden, dh $ o (n ^ 4) $.
ω - Notation
Wir gebrauchen ω-notationeine Untergrenze zu bezeichnen, die nicht asymptotisch eng ist. Formal definieren wir jedochω(g(n)) (kleines Omega von g von n) als Menge f(n) = ω(g(n)) für jede positive Konstante C > 0 und es existiert ein Wert $ n_ {0}> 0 $, so dass $ 0 \ leqslant cg (n) <f (n) $.
Zum Beispiel $ \ frac {n ^ 2} {2} = \ omega (n) $, aber $ \ frac {n ^ 2} {2} \ neq \ omega (n ^ 2) $. Die Beziehung $ f (n) = \ omega (g (n)) $ impliziert, dass die folgende Grenze existiert
$$ \ lim_ {n \ rightarrow \ infty} \ left (\ frac {f (n)} {g (n)} \ right) = \ infty $$
Das ist, f(n) wird relativ zu beliebig groß g(n) wie n nähert sich der Unendlichkeit.
Beispiel
Betrachten wir dieselbe Funktion: $ f (n) = 4.n ^ 3 + 10.n ^ 2 + 5.n + 1 $
Betrachtet man $ g (n) = n ^ 2 $,
$$ \ lim_ {n \ rightarrow \ infty} \ left (\ frac {4.n ^ 3 + 10.n ^ 2 + 5.n + 1} {n ^ 2} \ right) = \ infty $$
Daher die Komplexität von f(n) kann als $ o (g (n)) $ dargestellt werden, dh $ \ omega (n ^ 2) $.
Apriori- und Apostiari-Analyse
Apriori-Analyse bedeutet, dass die Analyse durchgeführt wird, bevor sie auf einem bestimmten System ausgeführt wird. Diese Analyse ist eine Phase, in der eine Funktion anhand eines theoretischen Modells definiert wird. Daher bestimmen wir die zeitliche und räumliche Komplexität eines Algorithmus, indem wir nur den Algorithmus betrachten, anstatt ihn auf einem bestimmten System mit einem anderen Speicher, Prozessor und Compiler auszuführen.
Die Apostiari-Analyse eines Algorithmus bedeutet, dass wir die Analyse eines Algorithmus erst durchführen, nachdem er auf einem System ausgeführt wurde. Es hängt direkt vom System ab und ändert sich von System zu System.
In einer Branche können wir keine Apostiari-Analyse durchführen, da die Software im Allgemeinen für einen anonymen Benutzer erstellt wurde, der sie auf einem anderen System als dem in der Branche vorhandenen ausführt.
In Apriori verwenden wir aus diesem Grund asymptotische Notationen, um die zeitliche und räumliche Komplexität zu bestimmen, wenn sie sich von Computer zu Computer ändern. asymptotisch sind sie jedoch gleich.