Landau-Notation - Versionsgeschichte

Css am 25. August 2018 um 19:07 Uhr

2018-08-25T19:07:51Z

Css am 25. August 2018 um 19:07 Uhr

2018-08-25T19:07:29Z

Css am 25. August 2018 um 19:06 Uhr

2018-08-25T19:06:36Z

Css am 26. Juli 2018 um 14:38 Uhr

2018-07-26T14:38:28Z

Css am 26. Juli 2018 um 14:36 Uhr

2018-07-26T14:36:37Z

Css am 26. Juli 2018 um 14:35 Uhr

2018-07-26T14:35:03Z

Css am 26. Juli 2018 um 14:31 Uhr

2018-07-26T14:31:12Z

Css am 26. Juli 2018 um 14:20 Uhr

2018-07-26T14:20:45Z

Css: 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…“

2018-07-26T14:19:13Z

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…“

Neue Seite

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.

← Nächstältere Version		Version vom 25. August 2018, 19:07 Uhr
Zeile 11:		Zeile 11:
	* Jedes Polynom $p$ ist in ${\cal O}(e^x)$.		* Jedes Polynom $p$ ist in ${\cal O}(e^x)$.

−	Seien $f$ und $g$ zwei Funktionen von $\mathbb{R}$ nach $\mathbb{R}$. Wir sagen $f\in{\cal o}(g)$, wenn für alle $\varepsilon>0$ ein $N$ existiert, sodass für alle $n\ge N$ gilt $\|f(x)\|\le\varepsilon \|g(x)\|$. Das heißt, $f$ wird beliebig klein gegenüber $g$.	+	Seien $f$ und $g$ zwei Funktionen von $\mathbb{R}$ nach $\mathbb{R}$. Wir sagen $f\in{\cal o}(g)$, wenn für alle $\varepsilon>0$ ein $N$ existiert, sodass für alle $n\ge N$ gilt $\|f(n)\|\le\varepsilon \|g(n)\|$. Das heißt, $f$ wird beliebig klein gegenüber $g$.

← Nächstältere Version		Version vom 25. August 2018, 19:07 Uhr
Zeile 11:		Zeile 11:
	* Jedes Polynom $p$ ist in ${\cal O}(e^x)$.		* Jedes Polynom $p$ ist in ${\cal O}(e^x)$.

−	Seien $f$ und $g$ zwei Funktionen von $\mathbb{R}$ nach $\mathbb{R}$. Wir sagen $f\in{\cal o}(g)$, wenn für alle $\varepsilon$ ein $N$ existiert, sodass für alle $n\ge N$ gilt $\|f(x)\|\le\varepsilon g(x)$. Das heißt, $f$ wird beliebig klein gegenüber $g$.	+	Seien $f$ und $g$ zwei Funktionen von $\mathbb{R}$ nach $\mathbb{R}$. Wir sagen $f\in{\cal o}(g)$, wenn für alle $\varepsilon>0$ ein $N$ existiert, sodass für alle $n\ge N$ gilt $\|f(x)\|\le\varepsilon \|g(x)\|$. Das heißt, $f$ wird beliebig klein gegenüber $g$.

← Nächstältere Version		Version vom 25. August 2018, 19:06 Uhr
Zeile 10:		Zeile 10:
	* Funktionen in ${\cal O}(1)$ sind ab hinreichend großer Eingabe durch eine Konstante beschränkt.		* Funktionen in ${\cal O}(1)$ sind ab hinreichend großer Eingabe durch eine Konstante beschränkt.
	* Jedes Polynom $p$ ist in ${\cal O}(e^x)$.		* Jedes Polynom $p$ ist in ${\cal O}(e^x)$.
		+
		+	Seien $f$ und $g$ zwei Funktionen von $\mathbb{R}$ nach $\mathbb{R}$. Wir sagen $f\in{\cal o}(g)$, wenn für alle $\varepsilon$ ein $N$ existiert, sodass für alle $n\ge N$ gilt $\|f(x)\|\le\varepsilon g(x)$. Das heißt, $f$ wird beliebig klein gegenüber $g$.

← Nächstältere Version		Version vom 26. Juli 2018, 14:38 Uhr
Zeile 9:		Zeile 9:
	* Seien $p$ und $q$ Polynome, und $\deg p \le \deg q$. Dann ist $p\in{\cal O}(q)$. Deshalb schreibt man meistens nur die höchste Potenz hin, also zum Beispiel ${\cal O}(x^4)$.		* Seien $p$ und $q$ Polynome, und $\deg p \le \deg q$. Dann ist $p\in{\cal O}(q)$. Deshalb schreibt man meistens nur die höchste Potenz hin, also zum Beispiel ${\cal O}(x^4)$.
	* Funktionen in ${\cal O}(1)$ sind ab hinreichend großer Eingabe durch eine Konstante beschränkt.		* Funktionen in ${\cal O}(1)$ sind ab hinreichend großer Eingabe durch eine Konstante beschränkt.
		+	* Jedes Polynom $p$ ist in ${\cal O}(e^x)$.

@@ Zeile 7: / Zeile 7: @@
 Beispiele:
-* 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)$. Deshalb schreibt man meistens nur die höchste Potenz hin, also zum Beispiel ${\cal O}(x^4)$.
 * Funktionen in ${\cal O}(1)$ sind ab hinreichend großer Eingabe durch eine Konstante beschränkt.

← Nächstältere Version		Version vom 26. Juli 2018, 14:35 Uhr
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.

← Nächstältere Version		Version vom 26. Juli 2018, 14:31 Uhr
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 $0<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.
		+
		+	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)$.

← Nächstältere Version		Version vom 26. Juli 2018, 14:20 Uhr
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.