[DSAL] beweise mit der O-Notation

[Progra] Programmierung
[DSAL] Datenstrukturen und Algorithmen
[SWT] Softwaretechnik
[DB] Datenbanken und Informationssysteme

beweise mit der O-Notation

Beitragvon paco89 » 17.04.11 01:38

hi,

wie beweise ich folgende aussage:

n^logn = O ((logn)^n)


wie geht man bei solchen sachen vor??? hab kein plan...bitte um hilfe...
Zuletzt geändert von AGo am 17.04.11 14:08, insgesamt 1-mal geändert.
Grund: Das ist ein DaStru Thema und keins aus einer Mathe-VL
paco89
 
Beiträge: 115
Registriert: 05.12.10 05:04

Re: beweise mit der O-Notation

Beitragvon ZaKaRy » 17.04.11 09:58

Naja, da weiß ich nicht was man da beweisen soll. Das man

log(n^n) als nlog(n)

schreiben kann ist ein Logarithmusgesetz, hab noch nie gesehen, dass man die Logarithmengesetze beweisen muss.

Edith: Hab ne Klammer übersehen. Ist aber eigentlich auch nicht schwerer, da der Logarithmus ja monoton steigend und ab n>1 positiv ist hab ich auf beiden Seiten ab z.b. ab n=2 etwas positives stehen. Da Exponetialfunktionen schneller wachsen als lineare gilt dann nlog(n) \in (log(n))^n. Dass sollte man dann formal aufschreiben und gut ist.

Edith 2: Ok da steht nicht nlog(n) sondern n^{log(n)} auf der linken Seite der Gleichung. Da muss ich nochmal drüber nachdenken. Wenn du Tex-tags benutzt, kann man die Aufgabe besser lesen :-)
Ich würde vorschlagen, du zeigst, dass log(n) \in O(n) gilt, dann haste im Prinzip deine Aufgabe gelöst.
Zuletzt geändert von ZaKaRy am 17.04.11 10:17, insgesamt 7-mal geändert.
Benutzeravatar
ZaKaRy
 
Beiträge: 225
Registriert: 12.09.07 18:28
Wohnort: Aachen
Studiengang: Lehramt
Studiert seit: fertig
Anwendungsfach: Mathe

Re: beweise mit der O-Notation

Beitragvon mirko » 17.04.11 10:08

schau dir eure definition der O-Notation an. da dürfte sowas stehen wie f(n) =* O(g(n)) gdw ...

dann prüfst du, ob "..." für f(n)=n^logn und g(n)=(logn)^n gilt.

--

*) lies \in
mirko
 
Beiträge: 1032
Registriert: 22.10.06 18:33
Studiert seit: WS 12/13

Re: beweise mit der O-Notation

Beitragvon m.singh » 17.04.11 18:27

du kannst es auch über dem limes berechen. Laut definition ist die O-Notation folgendermaßen definiert: limes n->unendlich g(x)/f(x) --> [0;unendlich)

jetzt einfach die beiden funktionen als Quotienten schreiben und versuchen nach ein paar logarithmen gesetzen zu vereinfachen. Irgendwann wirst du den Grenzwert bestimmen können.

Tipp: f(x) = 10^log(f(x))
m.singh
 
Beiträge: 8
Registriert: 05.04.11 18:28
Studiengang: Informatik (B.Sc.)


Zurück zu Praktische Informatik