Forum "Uni-Sonstiges" - GROSS O Notation - Vorhilfe.de

Vorhilfe Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
	Hallo Gast! [ einloggen \| registrieren ]
	Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum

Forenbaum

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation

Startseite...
Neuerdings beta neu
Forum...
vorwissen...
vorkurse...
Werkzeuge...
Nachhilfevermittlung beta...
Online-Spiele beta
Suchen
Verein...
Impressum

Das Projekt

Server und Internetanbindung werden durch Spenden finanziert.

Organisiert wird das Projekt von unserem Koordinatorenteam.

Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.

Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".

Partnerseiten

Weitere Fächer:

Vorhilfe.de

FunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme

Forum "Uni-Sonstiges" - GROSS O Notation

GROSS O Notation < Sonstiges < Hochschule < Mathe < Vorhilfe

Ansicht:

[ geschachtelt ]

Forum "Uni-Sonstiges" |

Alle Foren |

Forenbaum | Materialien

GROSS O Notation: GROSS O Notation

Status:	(Frage) reagiert/warte auf Reaktion
Datum:	16:56 Mo 18.10.2004
Autor:	beronce

Hallo Leute!
Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt:http://www.htwm.de/~mathe/forum/viewtopic.php?p=227#227!!!!

Hoffe es kann mir jemand weiterhelfen!

1. Und zwar soll gezeigt werden dass n³ element von [mm] O(e^n) [/mm] ist!

Frage: kann man hier (bei der gross o notation) n0 und c frei wählen (um zu zeigen dass die Bedingung erfüllt wird), oder gibt's da einen Rechenschritt wie man beide/eines der beiden bestimmen kann!

2. Beweise O(f+g) = O(f) + O(g)

3. Beweise O(f+g) = O(f) wenn g element von O(f)

Vielen Dank!
LG

Bezug

GROSS O Notation: Tipps

Status:	(Antwort) fertig
Datum:	14:19 Di 19.10.2004
Autor:	Julius

Hallo Beronce!

Ich gebe dir mal ein paar Tipps:

> 1. Und zwar soll gezeigt werden dass n³ element von [mm]O(e^n)[/mm]
> ist!

Du weißt vielleicht, dass die Exponentialfunktion schneller wächst als jede Potenzfunktion. Daher gilt:

[mm] $\lim\limits_{n \to \infty} \frac{n^3}{e^n} [/mm] =0$.

Konvergente Folgen sind aber beschränkt...

> Frage: kann man hier (bei der gross o notation) n0 und c
> frei wählen (um zu zeigen dass die Bedingung erfüllt wird),
> oder gibt's da einen Rechenschritt wie man beide/eines der
> beiden bestimmen kann!

Du musst halt eine $C$ und ein (davon i.A. abhängiges) [mm] $n_0$ [/mm] finden, so dass die Bedingung erfüllt ist (oder aber wie ich oben anders argumentieren, wenn es denn geht).

> 2. Beweise O(f+g) = O(f) + O(g)

Du musst zeigen, dass die jeweils eine Menge in der anderen enthalten ist. Nehme also zunächst ein $h [mm] \in [/mm] O(f) + O(g)$ (also ein $h=f'+g'$ mit $f' [mm] \in [/mm] O(f)$ und $g' [mm] \in [/mm] O(g)$) und zeige, dass es in $O(f+g)$ liegt. Das geht recht einfach mit der Dreiecksungleichung. Die andere Richtung ist schwieriger: Hier musst du ein $h [mm] \in [/mm] O(f+g)$ wählen und zeigen, dass es sich in der Form $h=f'+g'$ mit $f' [mm] \in [/mm] O(f)$ und $g' [mm] \in [/mm] O(g)$ darstellbar ist.

(Ich würde es mal mit $h = [mm] \frac{hf}{f+g} [/mm] + [mm] \frac{hg}{f+g}$ [/mm] versuchen. ;-)

)

> 3. Beweise O(f+g) = O(f) wenn g element von O(f)

Die Inklusion [mm] "$\supset$" [/mm] ist aus 2. völlig klar (da $0 [mm] \in [/mm] O(g)$). Für die andere Richtung schätzt du in der Darstellung $h=f'+g'$ die Funktion $f'$ und $g'$ beide durch $f$ ab, was nach Voraussetzung möglich ist.

Jetzt will ich mal ein paar Ansätze von dir sehen, in denen du meine Tipps verarbeitest. :-)

Dann geht es weiter.