Beweis O-Notation < Numerik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Stellen Sie fest (mit Begründung!), ob die folgenden Aussagen wahr oder falsch sind.
(a) n! [mm] \in O(2^{2^{n}})?
[/mm]
(b) n! [mm] \in O(2^{4})?
[/mm]
(c) [mm] (log(n))^{log(n)} \in [/mm] O(n) |
Ich bin mir unsicher, wie ich diese Aufgaben lösen muss. f(n) [mm] \in [/mm] O(g(n)) bedeutet doch nichts anderes, als dass ab einem bestimmten Wert c f(n) [mm] \le [/mm] g(n), egal, wie groß man n wählt?
Ich habe schonmal versucht, (a) mittels vollständiger Induktion zu lösen:
IA: z.z.: n! [mm] \le 2^{2^{n}} [/mm] für n = 0
0! = 0
[mm] 2^{2^{0}} [/mm] = 2
0 [mm] \le [/mm] 2
IV: gelte n! [mm] \le 2^{2^{n}} [/mm] für ein beliebiges n
IB: z.z.: ...dann gilt auch (n+1)! [mm] \le 2^{2^{n+1}}
[/mm]
(n+1)! = n! * (n+1)
[mm] 2^{2^{n+1}} [/mm] = [mm] 2^{2^{n}*2} [/mm] = [mm] 2^{2^{n}} [/mm] * [mm] 2^{2^{n}}
[/mm]
(n+1) [mm] \le 2^{2^{n}}
[/mm]
[mm] \Rightarrow 2^{2^{n}} [/mm] wächst schneller als n!
[mm] \Rightarrow [/mm] n! [mm] \in O(2^{2^{n}}) [/mm] gilt
Kann man das so machen?
Aufgabe (b) würde ich ähnlich angehen. Bei (c) bin ich mir noch nicht sicher, da mir generell noch das nötige Hintergrundwissen zu Logarithmen fehlt.
Ich würde gerne wissen, ob mein Ansatz überhaupt klappt oder ich bereits jetzt auf dem Holzweg bin  .
Vielen Dank im Voraus!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 00:16 So 29.04.2012 | | Autor: | huzein |
hi,
> (n+1) [mm] \le 2^{2^{n}}
[/mm]
hier bist du noch nicht fertig, denn du willst ja
> IB: z.z.: ...dann gilt auch (n+1)! [mm]\le 2^{2^{n+1}}[/mm]
zeigen. eine letzte Abschätzung würde also noch fehlen. auch wenn die offensichtlich ist, sollte man sie hinschreiben.
Gruß
|
|
|
| |
|
| Aufgabe | Stellen Sie fest (mit Begründung!), ob die folgenden Aussagen wahr oder falsch sind.
(a) n! $ [mm] \in O(2^{2^{n}})? [/mm] $
(b) n! $ [mm] \in O(2^{4})? [/mm] $
(c) $ [mm] (log(n))^{log(n)} \in [/mm] $ O(n) |
Ok, danke für den Hinweis . Hast du auch noch einen Tipp insbesondere zu Aufgabe (c)?
Liebe Grüße
Katzenpfoetchen
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:18 So 29.04.2012 | | Autor: | huzein |
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Naja ich würde versuchen mit der exp Funktion zu argumentieren. Setze $y:=\ln (x)$ dann hast du den Ausdruck
$(\ln x)^{\ln x} =y^y=e^{y\cdot \ln y$.
Und man weiß dass
y=o(e^y) für y\to\infty
bzw, dass
\lim\limits_{y\to\infty}\dfrac{y}{e^y}=0
Damit würde ich versuchen was zu machen.
Gruß
|
|
|
|
