Landau-Notation

04.05.2022, 16:47

LostinMathe28

Landau-Notation

Meine Frage:
Hallo, ich bräuchte Hilfe bei den angehängten Aufgaben, da ich leider nicht verstehe wie genau man die Aussagen beweisen oder wiederlegen kann. Wäre nett wenn mir jemand dabei helfen könnte.

Meine Ideen:
Leider weiß ich nicht wie man hier vorgehen soll, daher benötige ich Hilfe

04.05.2022, 17:26

HAL 9000

Auf diesen Beitrag antworten »

a) und f) sind richtig, für alle anderen findet man Gegenbeispiele - zu b) gebe ich mal ein mögliches an:

$\begin{eqnarray*} f_1(n)=f_3(n)=g_1(n) = n,~g_2(n)=1-n \end{eqnarray*}$

Vielleicht inspiriert dich das, auch welche für die anderen Teilaufgaben zu finden.

04.05.2022, 17:33

Finn_

Auf diesen Beitrag antworten »

Der Beweis von a) geht beispielsweise wie folgt. Laut der Definition

$\begin{eqnarray*} f\in\mathcal O(g) \iff \exists c>0\colon \exists n_0\colon\forall n>n_0\colon |f(n)|\le c|g(n)| \end{eqnarray*}$

sind die Prämissen

$\begin{eqnarray*} \exists c>0\colon \exists n_0\colon\forall n>n_0\colon |f_1(n)|\le c|g_1(n)|, \end{eqnarray*}$
$\begin{eqnarray*} \exists c'>0\colon \exists n_0'\colon\forall n>n_0'\colon |f_2(n)|\le c'|g_1(n)| \end{eqnarray*}$

gegeben. Mit der Dreiecksungleichung findet sich

$\begin{eqnarray*} |f_1(n)+f_2(n)|\le |f_1(n)|+|f_2(n)|\le c|g_1(n)| + c'|g_1(n)| = (c+c')|g_1(n)| \end{eqnarray*}$

für $\begin{eqnarray*} n>\max(n_0,n_0'). \end{eqnarray*}$ Ergo haben wir Zeugen $\begin{eqnarray*} c'':=c+c' \end{eqnarray*}$ und $\begin{eqnarray*} n_0'':=\max(n_0,n_0') \end{eqnarray*}$ für die Existenzaussage

$\begin{eqnarray*} \exists c''>0\colon \exists n_0''\colon\forall n>n_0''\colon |f_1(n)+f_2(n)|\le c''|g_1(n)|. \end{eqnarray*}$

05.05.2022, 15:55

28DM

Auf diesen Beitrag antworten »

Hey, ich habe eine ähnliche Aufgabe, könntest du vielleicht erklären wie genau das von dir erwähnte Beispiel die b widerlegt? @HAL 9000

05.05.2022, 16:10

28DM

Auf diesen Beitrag antworten »

Noch eine Anmerkung, bezüglich der c) habe ich hier etwas gefunden. Allerdings gilt die Aussage nur für asymptotisch nicht-negative Funktionen, oder?

05.05.2022, 17:42

HAL 9000

Auf diesen Beitrag antworten »

Das Finden solcher Beispiele mag noch eine Herausforderung sein - das Überprüfen hingegen ist doch nun wirklich nicht schwer: Einsetzen in die Definitionen und schauen, ob es klappt!!!

Na gut, stellen wir es beim oben genannten Gegenbeispiel von b) mal dar:

$\begin{eqnarray*} f_1(n)\in \mathcal{O}\left(g_1(n)\right) \end{eqnarray*}$ bedeutet (siehe Finn): $\begin{eqnarray*} \exists c>0\colon \exists n_0\colon\forall n>n_0\colon |f_1(n)|\le c|g_1(n)| \end{eqnarray*}$

Im vorliegenden Fall gilt $\begin{eqnarray*} \left|n\right| \leq 1\cdot \left|n\right| \end{eqnarray*}$ für alle $\begin{eqnarray*} n \end{eqnarray*}$ , also klappt das mit $\begin{eqnarray*} c=1 \end{eqnarray*}$ und beliebigem $\begin{eqnarray*} n_0 \end{eqnarray*}$

Nun zu $\begin{eqnarray*} f_3(n)\in \mathcal{O}\left(g_2(n)\right) \end{eqnarray*}$ , d.h. $\begin{eqnarray*} \exists c>0\colon \exists n_0\colon\forall n>n_0\colon |f_3(n)|\le c|g_2(n)| \end{eqnarray*}$ :

Es gilt $\begin{eqnarray*} n = \left|n\right| \leq 2\cdot \left|1-n\right| = 2n-2 \end{eqnarray*}$ für alle $\begin{eqnarray*} n\geq 2 \end{eqnarray*}$ , also klappt das mit $\begin{eqnarray*} c=2 \end{eqnarray*}$ sowie $\begin{eqnarray*} n_0=2 \end{eqnarray*}$ .

Damit sind die Voraussetzungen erfüllt. Für Behauptung $\begin{eqnarray*} f_1(n)+f_3(n)\in \mathcal{O}\left(g_1(n)+g_2(n)\right) \end{eqnarray*}$ müsste nun gelten

$\begin{eqnarray*} \exists c>0\colon \exists n_0\colon\forall n>n_0\colon |f_1(n)+f_3(n)|\le c|g_1(n)+g_2(n)| \end{eqnarray*}$ , eingesetzt

$\begin{eqnarray*} \exists c>0\colon \exists n_0\colon\forall n>n_0\colon 2n\le c\cdot 1 \end{eqnarray*}$

Ein solches $\begin{eqnarray*} c \end{eqnarray*}$ gibt es nicht, da die linke Seite $\begin{eqnarray*} 2n \end{eqnarray*}$ unbeschränkt wächst.

----------------------------------

Eine erhebliche Erleichterung ergibt sich, wenn man sich folgendes überlegt (und ein für alle mal nachweist):

Zitat:

Für Polynomfunktionen $\begin{eqnarray*} f,g \end{eqnarray*}$ gilt $\begin{eqnarray*} f(n)\in \mathcal{O}\left(g(n)\right) \end{eqnarray*}$ genau dann, wenn der Grad von $\begin{eqnarray*} f \end{eqnarray*}$ höchstens so groß ist wie der von $\begin{eqnarray*} g \end{eqnarray*}$ .

----------------------------------

Zitat:

Original von 28DM
Noch eine Anmerkung, bezüglich der c) habe ich hier etwas gefunden. Allerdings gilt die Aussage nur für asymptotisch nicht-negative Funktionen, oder?

Ich sehe kein "hier". Es ist allerdings richtig, dass einige der Gegenbeispiele oben nur mit negativen Vergleichsfunktionen funktionieren, z.B. eben bei b). In deinen Voraussetzungen oben war aber ja keine Rede von irgendwelchen Nichtnegativitätsforderungen an $\begin{eqnarray*} g_1,g_2 \end{eqnarray*}$ o.ä.

Neue Frage »

Antworten »

Landau-Notation

Verwandte Themen