Landau Symbole < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:04 Sa 25.12.2010 | | Autor: | pyw |
| Aufgabe | Ordnen Sie die folgenden Funktionen in einer Reihenfolge [mm] g_1, g_2, \ldots, g_7 [/mm] an, sodass gilt [mm] g_1\in O(g_2), g_2\in O(g_3), \ldots, g_6\in O(g_7):
[/mm]
[mm] \log(n!), [/mm] n!, 9, [mm] \log^2 [/mm] n, [mm] \log\log [/mm] n, [mm] \sqrt{\log(3n)}, (\log n)^{\log n} [/mm]
Beweisen Sie die Richtigkeit der Reihenfolge. |
Hallo,
Sei die Relation [mm] \sim [/mm] zwischen zwei Funktionen gegeben durch: [mm] f\sim [/mm] g [mm] \gdw f\in [/mm] O(g). (vgl. Landau-Notation). [mm] \sim [/mm] ist transitiv. Dann bin ich mir sicher, dass das hier eine gesuchte Reihenfolge ist:
9 [mm] \sim \log\log [/mm] n [mm] \sim\sqrt{\log(3n)}\sim\log^2 n\sim(\log n)^{\log n}\sim\log(n!)\sim [/mm] n!
Aufgrund der Transitivität brauche ich nur jeweils zeigen, dass zwei benachbarte in dieser Kette in Relation stehen. Bei zweien schaffe ich das leider nicht:
1. [mm] \log\log [/mm] n [mm] \sim\sqrt{\log(3n)}
[/mm]
2. [mm] (\log n)^{\log n}\sim\log(n!)
[/mm]
Kann mir bitte jemand helfen? Ich weiß, dass ich zum Nachweis von [mm] f\sim [/mm] g zum Beispiel eine Konstante c finden kann, für die für alle [mm] n\geq n_0 [/mm] gilt [mm] f(n)\leq c\cdot [/mm] g(n)
Frohe Weihnachten!
und Danke für Hilfe im Voraus 
mfg pyw
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:32 Sa 25.12.2010 | | Autor: | felixf |
Moin!
> Ordnen Sie die folgenden Funktionen in einer Reihenfolge
> [mm]g_1, g_2, \ldots, g_7[/mm] an, sodass gilt [mm]g_1\in O(g_2), g_2\in O(g_3), \ldots, g_6\in O(g_7):[/mm]
>
> [mm]\log(n!),[/mm] n!, 9, [mm]\log^2[/mm] n, [mm]\log\log[/mm] n, [mm]\sqrt{\log(3n)}, (\log n)^{\log n}[/mm]
>
> Beweisen Sie die Richtigkeit der Reihenfolge.
> Hallo,
>
> Sei die Relation [mm]\sim[/mm] zwischen zwei Funktionen gegeben
> durch: [mm]f\sim[/mm] g [mm]\gdw f\in[/mm] O(g). (vgl. Landau-Notation).
Das ist eine nette Idee, aber der Name ist etwas gefaehrlich: man benutzt [mm] $\sim$ [/mm] meist fuer etwas staerkeres, naemlich wenn zusaetzlich gilt $g [mm] \in [/mm] O(f)$, oder wenn die Konstanten sogar 1 sein muessen (also wenn [mm] $\lim_{n\to\infty} \frac{f(n)}{g(n)} [/mm] = 1$ ist).
> [mm]\sim[/mm]
> ist transitiv. Dann bin ich mir sicher, dass das hier eine
> gesuchte Reihenfolge ist:
>
> 9 [mm]\sim \log\log[/mm] n [mm]\sim\sqrt{\log(3n)}\sim\log^2 n\sim(\log n)^{\log n}\sim\log(n!)\sim[/mm]
> n!
>
> Aufgrund der Transitivität brauche ich nur jeweils zeigen,
> dass zwei benachbarte in dieser Kette in Relation stehen.
> Bei zweien schaffe ich das leider nicht:
>
> 1. [mm]\log\log[/mm] n [mm]\sim\sqrt{\log(3n)}[/mm]
> 2. [mm](\log n)^{\log n}\sim\log(n!)[/mm]
Also alle [mm] $\sim$'s [/mm] aus der Kette oben ungleich diesen hier stimmen, um das erstmal klarzustellen.
> Kann mir bitte jemand helfen? Ich weiß, dass ich zum
> Nachweis von [mm]f\sim[/mm] g zum Beispiel eine Konstante c finden
> kann, für die für alle [mm]n\geq n_0[/mm] gilt [mm]f(n)\leq c\cdot[/mm]
> g(n)
Es ist [mm] $\sqrt{\log(3n)} [/mm] = [mm] \sqrt{\log n + \log 3} \ge \sqrt{\log n}$. [/mm] Es reicht also zu zeigen, dass [mm] $\log [/mm] x [mm] \le \sqrt{x}$ [/mm] ist fuer $x [mm] \ge x_0$: [/mm] daraus folgt mit [mm] $\log [/mm] n [mm] \ge x_0$ [/mm] (also $n [mm] \ge \exp(x_0)$), [/mm] dass [mm] $\log \log [/mm] n [mm] \le \sqrt{\log n} \le \sqrt{\log(3 n)}$ [/mm] ist.
Kannst du [mm] $\log [/mm] x [mm] \le \sqrt{x}$ [/mm] fuer gross genuges $x$ zeigen? (Schau dir einfach [mm] $\lim_{x\to\infty} \frac{\sqrt(x)}{\log x}$ [/mm] an; wenn das $< 1$ ist, dann gibt es ein [mm] $x_0$ [/mm] mit [mm] $\log [/mm] x [mm] \le \sqrt{x}$ [/mm] fuer alle $x [mm] \ge x_0$.)
[/mm]
Und jetzt zu [mm] $(\log n)^{\log n}$ [/mm] und [mm] $\log [/mm] n!$. Da hast du die Reihenfolge falsch: [mm] $\log [/mm] n! = [mm] \sum_{i=1}^n \log [/mm] i [mm] \le [/mm] n [mm] \log [/mm] n$ ist fuer grosses $n$ kleiner als [mm] $(\log n)^{\log n}$.
[/mm]
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:49 Sa 25.12.2010 | | Autor: | pyw |
> Es ist [mm]\sqrt{\log(3n)} = \sqrt{\log n + \log 3} \ge \sqrt{\log n}[/mm].
> Es reicht also zu zeigen, dass [mm]\log x \le \sqrt{x}[/mm] ist fuer
> [mm]x \ge x_0[/mm]: daraus folgt mit [mm]\log n \ge x_0[/mm] (also [mm]n \ge \exp(x_0)[/mm]),
> dass [mm]\log \log n \le \sqrt{\log n} \le \sqrt{\log(3 n)}[/mm]
> ist.
>
> Kannst du [mm]\log x \le \sqrt{x}[/mm] fuer gross genuges [mm]x[/mm] zeigen?
> (Schau dir einfach [mm]\lim_{x\to\infty} \frac{\sqrt(x)}{\log x}[/mm]
> an; wenn das [mm]< 1[/mm] ist, dann gibt es ein [mm]x_0[/mm] mit [mm]\log x \le \sqrt{x}[/mm]
> fuer alle [mm]x \ge x_0[/mm].)
Du meinst sicherlich [mm]\lim_{x\to\infty} \frac{\log x}{\sqrt(x)}\stackrel{L'Hospital}{=}\lim_{x\to\infty} \frac{1/x}{0.5x^{-0.5}}=\lim_{x\to\infty} \frac{1}{0.5\sqrt{x}}=0<1[/mm]. Deswegen gibt es das [mm]x_0[/mm] mit [mm]\log x \le \sqrt{x}[/mm] fuer alle [mm]x \ge x_0[/mm]. Danke so gehts!
>
>
> Und jetzt zu [mm](\log n)^{\log n}[/mm] und [mm]\log n![/mm]. Da hast du die
> Reihenfolge falsch: [mm]\log n! = \sum_{i=1}^n \log i \le n \log n[/mm]
> ist fuer grosses [mm]n[/mm] kleiner als [mm](\log n)^{\log n}[/mm].<
Oh, da hab ich mich vertan. Danke für den Hinweis.
>
> LG Felix
>
lg pyw
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:25 Sa 25.12.2010 | | Autor: | felixf |
Moin,
> > Kannst du [mm]\log x \le \sqrt{x}[/mm] fuer gross genuges [mm]x[/mm] zeigen?
> > (Schau dir einfach [mm]\lim_{x\to\infty} \frac{\sqrt(x)}{\log x}[/mm]
> > an; wenn das [mm]< 1[/mm] ist, dann gibt es ein [mm]x_0[/mm] mit [mm]\log x \le \sqrt{x}[/mm]
> > fuer alle [mm]x \ge x_0[/mm].)
>
> Du meinst sicherlich
> [mm]\lim_{x\to\infty} \frac{\log x}{\sqrt(x)}\stackrel{L'Hospital}{=}\lim_{x\to\infty} \frac{1/x}{0.5x^{-0.5}}=\lim_{x\to\infty} \frac{1}{0.5\sqrt{x}}=0<1[/mm].
> Deswegen gibt es das [mm]x_0[/mm] mit [mm]\log x \le \sqrt{x}[/mm] fuer alle
> [mm]x \ge x_0[/mm]. Danke so gehts!
genau, so geht das am schnellsten 
> > Und jetzt zu [mm](\log n)^{\log n}[/mm] und [mm]\log n![/mm]. Da hast du die
> > Reihenfolge falsch: [mm]\log n! = \sum_{i=1}^n \log i \le n \log n[/mm]
> > ist fuer grosses [mm]n[/mm] kleiner als [mm](\log n)^{\log n}[/mm].<
>
> Oh,
> da hab ich mich vertan. Danke für den Hinweis.
Bitte!
LG Felix
|
|
|
|
