Landau-Notation: Unterschied zwischen den Versionen
Css (Diskussion | Beiträge) |
Css (Diskussion | Beiträge) |
||
| Zeile 8: | Zeile 8: | ||
* Seien $p$ und $q$ Polynome, und $\deg p \le \deg q$. Dann ist $p\in{\cal O}(q)$. | * Seien $p$ und $q$ Polynome, und $\deg p \le \deg q$. Dann ist $p\in{\cal O}(q)$. | ||
| + | * Funktionen in ${\cal O}(1)$ sind ab hinreichend großer Eingabe durch eine Konstante beschränkt. | ||
Version vom 26. Juli 2018, 16:35 Uhr
Beim Vergleichen von Laufzeiten und Speicherplatz ist es oft nicht sinnvoll, diese bis auf lineare Faktoren genau anzugeben. Insbesondere kommt es des Öfteren vor, dass Dinge für kleine Eingaben andere Eigenschaften haben als für größere Eingaben. Deshalb behilft man sich, indem man nur das asymptotische Verhalten betrachtet.
Seien $f$ und $g$ zwei Funktionen von $\mathbb{R}$ nach $\mathbb{R}$. Wir sagen $f\in{\cal O}(g)$, wenn eine Konstante $0<c\in\mathbb{R}$ existiert, sodass für hinreichend groß gewähltes $x$ stets $|f(x)| < c\cdot |g(x)|$ gilt.
Oft schreibt man, zum Beispiel in der Numerik, $f={\cal O}(g)$ statt $f\in{\cal O}(g)$.
Beispiele:
- Seien $p$ und $q$ Polynome, und $\deg p \le \deg q$. Dann ist $p\in{\cal O}(q)$.
- Funktionen in ${\cal O}(1)$ sind ab hinreichend großer Eingabe durch eine Konstante beschränkt.
