Laufzeit O(n) < Funktionen < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 00:04 Do 18.05.2006 | | Autor: | Lavanya |
| Aufgabe | Seien k,d [mm] \in \IN [/mm] beliebig aber fest.Beweise:
1. [mm] k^{n+d}\in [/mm] O( [mm] k^{n}) [/mm] mit d>1
2. [mm] k^{dn} \not\in O(k^{n}) [/mm] mit d>1
3. [mm] n^{n} \in O(2^{n^{2}})
[/mm]
4. [mm] log^{k}*n \in [/mm] O( [mm] \wurzel{n})
[/mm]
5. Seien [mm] f,g:\IN \to\IN:Funktionen. [/mm] Dann gilt :
[mm] \limes_{n\rightarrow\infty} \bruch{g(n)}{f(n)}=k\in\IR^{>0} >g\in [/mm] O(f)
6. [mm] \limes_{n\rightarrow\infty} \bruch{g(n)}{f(n)}= \infty\in\IR^{>0} >g\in [/mm] O(f)
|
Hallo ihr lieben...........
Könnt ihr mir vielleicht sagen, wie ich das beweisen kann ???? Ich weiß nicht , wo ich anfangen muss......und vor allem wie !!!!!!
wäre super ......
danke
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 00:38 Do 18.05.2006 | | Autor: | leduart |
Hallo Lavanya
Man fängt IMMER damit an, die genauen Definitionen von O und o hinzuschreiben! und dann die einzelnen Aufgaben nachzusehen, ob sie erfüllt sind!
Fang erstmal damit an, und frag dann was genauer!
|
|
|
| |
|
Hallo und guten Morgen,
erstens: was hat das mit Linearer Algebra zu tun ? Ich werd es gleich unter ''Reelle Analysis'' ablegen, in Ordnung ?
Zweitens: Häufig ist es bei derlei Aufgaben gut, zu logarithmieren. Gilt [mm] \log [/mm] f(n) [mm] \leq c\cdot \log [/mm] g(n) mit c<1, so folgt zB f(n)=o(g(n)).
Wenn man sowas benutzt, muss man es natürlich vorher beweisen.
Als Anschubhilfe schreib ich Dir was zur ersten Teilaufgabe, schau aber die Def. vorher nach, die schreib ich nicht nochmal dazu.
Es ist [mm] k^{n+d}=k^d\cdot k^n, [/mm]
und [mm] k^d [/mm] ist ja, da k und d konstant sind, auch eine Konstante.
Gruss + viel Erfolg,
Mathias
|
|
|
|
