Welche Funktionen sind im Schnitt?

13.05.2022, 08:04

28AM

Landau-Notation // Welche Funktionen sind im Schnitt?

Meine Frage:
Es geht um die Aufgabe im angehängten Bild, bei der ich nicht weiterkomme.

Meine Ideen:
Ich komme bei der Aufgabe nicht weiter und bräuchte daher Hilfe.

13.05.2022, 10:09

HAL 9000

Auf diesen Beitrag antworten »

Es gibt keine Funktionen in diesem Durchschnitt. Die Begründung hängt stark davon ab, mit welcher Definition der Landau-Symbole $\begin{eqnarray*} o \end{eqnarray*}$ bzw. $\begin{eqnarray*} \omega \end{eqnarray*}$ du arbeiten willst (auf https://de.wikipedia.org/wiki/Landau-Symbole finden sich jeweils drei im Detail verschiedene Formulierungen der Definition für jedes Landau-Symbol).

P.S.: Es wäre übrigens nicht nötig gewesen, sowohl einen neuen Benutzer-Account anzulegen als auch einen neuen Thread zu eröffnen - der alte

Welche Funktionen sind im Schnitt von o(f) und w(f) ?

hätte es auch getan.

13.05.2022, 10:42

28DM

Auf diesen Beitrag antworten »

Wie kann man das denn zeigen für die Definitionen wie in Notation 3 auf Wikipedia, nur ohne die Betragsstriche?

Willkommen im Matheboard!

Du hast mittlerweile fünf Accounts, die User 28AM, 2AM8, MysteriöserD und Mysteriöser_D werden daher demnächst wieder gelöscht.

Viele Grüße
Steffen

13.05.2022, 11:11

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von 28DM
wie in Notation 3 auf Wikipedia, nur ohne die Betragsstriche?

Nun, auf die Betragsstriche bei $\begin{eqnarray*} f \end{eqnarray*}$ kann man verzichten, da ja laut $\begin{eqnarray*} f:\;\mathbb{N}\to \mathbb{R}_{\geq 0} \end{eqnarray*}$ sowieso $\begin{eqnarray*} f(n)\geq 0 \end{eqnarray*}$ für alle $\begin{eqnarray*} n \end{eqnarray*}$ vorgegeben ist.

Aber für die einzuordnenden Funktionen $\begin{eqnarray*} h \end{eqnarray*}$ (d.h. mit $\begin{eqnarray*} h\in o(f) \end{eqnarray*}$ oder $\begin{eqnarray*} h\in \omega(f) \end{eqnarray*}$ ) sind die Betragsstriche nur dann verzichtbar, wenn man sich von vornherein auch wieder auf $\begin{eqnarray*} h:\;\mathbb{N}\to \mathbb{R}_{\geq 0} \end{eqnarray*}$ einschränkt!!!

Es wäre jedenfalls bodenloser Schwachsinn, für die Funktionen $\begin{eqnarray*} f(n)=n \end{eqnarray*}$ sowie $\begin{eqnarray*} h(n)=-n^2 \end{eqnarray*}$ zu sagen $\begin{eqnarray*} h\in o(f) \end{eqnarray*}$ , weil ja tatsächlich für alle $\begin{eqnarray*} C>0 \end{eqnarray*}$ sowie $\begin{eqnarray*} n>0 \end{eqnarray*}$ die Ungleichung $\begin{eqnarray*} h(n) < C\cdot f(n) \end{eqnarray*}$ gilt - das widerspricht dem Sinn hinter den Landau-Symbolen. unglücklich

Neue Frage »

Antworten »

Landau-Notation // Welche Funktionen sind im Schnitt?

Verwandte Themen