Voraussetzung – Asymptotische Notationen , Eigenschaften asymptotischer Notationen , Analyse von Algorithmen
1. Big-O-Notation (O):
Es ist als Obergrenze definiert und die Obergrenze eines Algorithmus ist die höchste benötigte Zeit (die Leistung im schlechtesten Fall).
Big-O-Notation wird verwendet, um das zu beschreiben asymptotische Obergrenze .
Mathematisch gesehen, wenn f(n) beschreibt die Laufzeit eines Algorithmus; f(n) Ist O(g(n)) wenn es eine positive Konstante gibt C Und n0 so dass,
0 <= f(n) = n0
N = wird verwendet, um einer Funktion eine Obergrenze zu geben.
Wenn eine Funktion ist An) , es ist automatisch O(n-Quadrat) sowie.
Grafisches Beispiel für Großes O:
Arithmetik-Logikeinheit
2. Große Omega-Notation (Ω):
Es wird als untere Grenze definiert und die untere Grenze eines Algorithmus ist die geringste erforderliche Zeit (der effizienteste Weg, der möglich ist, mit anderen Worten der beste Fall).
So wie Ö Notation eine bereitstellen asymptotische Obergrenze , Oh Notation bietet asymptotische Untergrenze .
Lassen f(n) Laufzeit eines Algorithmus definieren;
f(n) wird gesagt, dass Ω(g(n)) wenn es eine positive Konstante gibt C Und (n0) so dass
0 <= Cg(n) = n0
Binärbaum vs. binärer Suchbaum
N = wird verwendet, um eine Untergrenze für eine Funktion anzugeben
Wenn eine Funktion ist Ω(n-Quadrat) es ist automatisch Oh(n) sowie.
Grafisches Beispiel für Großes Omega (Ω):
3. Big-Theta-Notation (Θ):
Es wird als engste Grenze definiert und die engste Grenze ist die beste aller Worst-Case-Zeiten, die der Algorithmus annehmen kann.
Lassen f(n) Definieren Sie die Laufzeit eines Algorithmus.
f(n) wird gesagt, dass Θ(g(n)) Wenn f(n) Ist O(g(n)) Und f(n) Ist Ω(g(n)).
Mathematisch,
0 <= f(n) = n0
0 <= C2g(n) = n0Wenn wir beide Gleichungen zusammenführen, erhalten wir:
0 <= C2g(n) <= f(n) = n0
Die Gleichung bedeutet einfach, dass es positive Konstanten C1 und C2 gibt, sodass f(n) zwischen C2 g(n) und C1g(n) liegt.
Grafisches Beispiel für Großes Theta (Θ) :
Zeichenfolge zum Chatten
Unterschied zwischen Big Oh, Big Omega und Big Theta:
| Ja Nein. | Big O | Großes Omega ( Oh) | Großes Theta (ICH) |
|---|---|---|---|
| 1. | Es ist wie (<=) Die Wachstumsrate eines Algorithmus ist kleiner oder gleich einem bestimmten Wert. | Es ist wie (>=) Die Wachstumsrate ist größer oder gleich einem bestimmten Wert. | Es ist wie (==) Das bedeutet, dass die Wachstumsrate einem bestimmten Wert entspricht. |
| 2. | Die Obergrenze des Algorithmus wird durch die Big-O-Notation dargestellt. Nur die obige Funktion ist durch Big O begrenzt. Die asymptotische Obergrenze wird durch die Big O-Notation angegeben. | Die Untergrenze des Algorithmus wird durch die Omega-Notation dargestellt. Die asymptotische Untergrenze wird durch die Omega-Notation angegeben. | Die Begrenzung der Funktion von oben und unten wird durch die Theta-Notation dargestellt. Das genaue asymptotische Verhalten wird durch diese Theta-Notation erreicht. |
| 3. | Großes O – Obergrenze | Big Omega (Ω) – Untergrenze | Big Theta (Θ) – Enge Grenze |
| 4. | Es wird als Obergrenze definiert und die Obergrenze eines Algorithmus ist die maximal erforderliche Zeit (die Leistung im schlechtesten Fall). | Es wird als untere Grenze definiert und die untere Grenze eines Algorithmus ist die geringste erforderliche Zeit (der effizienteste Weg, der möglich ist, mit anderen Worten der beste Fall). | Es wird als engste Grenze definiert und die engste Grenze ist die beste aller Worst-Case-Zeiten, die der Algorithmus annehmen kann. |
| 5. | Mathematisch gesehen: Big Oh ist 0 <= f(n) = n0 | Mathematisch gesehen: Big Omega ist 0 <= Cg(n) = n0 | Mathematisch gesehen ist Big Theta 0 <= C2g(n) <= f(n) = n0 |
Weitere Einzelheiten finden Sie unter: Design und Analyse von Algorithmen .