Landau-Notation: Unterschied zwischen den Versionen
Css (Diskussion | Beiträge) (Die Seite wurde neu angelegt: „Beim Vergleichen von Laufzeiten und Speicherplatz ist es oft nicht sinnvoll, diese bis auf lineare Faktoren genau anzugeben. Insbesondere kommt es des Öfteren…“) |
Css (Diskussion | Beiträge) |
||
| Zeile 1: | Zeile 1: | ||
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. | 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 $c\in\mathbb{R}$ existiert, sodass für hinreichend groß gewähltes $x$ stets $f(x) < c\cdot g(x)$ gilt. | + | 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. |
Version vom 26. Juli 2018, 16:20 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.
