Landau-Notation < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Aufgabe 5.) Beweisen oder widerlegen Sie folgende Behauptungen.
1. $n [mm] \cdot \log(n) \in [/mm] O(n)$
2. [mm] $\lfloor \log(n) \rfloor! \in O(n^{\log(\log(n))})$ [/mm] |
Hallo,
ich habe gerade einige Probleme bei der Landau-Notation und zwar muss ich bei 1. zeigen, dass eine superlineare Funktion von einer linearen Funktion von oben beschränkt werden kann, was meiner Meinung nach falsch wäre.
Somit wäre mein Ansatz $n [mm] \cdot \log(n) \notin [/mm] O(n) [mm] \Leftrightarrow \forall n_0 \in \IN, [/mm] c [mm] \in \IR^{+}: \exists [/mm] n [mm] \ge n_0: [/mm] c [mm] \cdot [/mm] n < n [mm] \cdot \log(n) \Rightarrow [/mm] c [mm] \cdot [/mm] n < n [mm] \cdot \log(n) \Leftrightarrow [/mm] c < [mm] \log(n) \Leftrightarrow a^c [/mm] < n$ (die Basis des Logarithmus war beliebig). Aber wie mache ich jetzt weiter (Auswahl von einem n und c) und stimmen die Schritte bisher?
zu 2.) Die Klammer steht übrigens für die Gaußklammer, also hier gilt [mm] $\lfloor \log(n) \rfloor! \in O(n^{\log(\log(n))}) \Leftrightarrow \exists n_0 \in \IN, [/mm] c [mm] \in \IR^+: \forall [/mm] n [mm] \ge n_0: \lfloor \log(n) \rfloor! \le [/mm] c [mm] \cdot n^{\log(\log(n))} \Rightarrow \lfloor \log(n) \rfloor! \le [/mm] c [mm] \cdot n^{\log(\log(n))} \Leftrightarrow \log(\frac{\lfloor \log(n) \rfloor!}{c}) \le \log(\log(n)) \cdot \log(n)$ [/mm]
Wie mache ich hier weiter?
Grüße
Joe
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:33 So 09.12.2012 | | Autor: | felixf |
Moin!
> Aufgabe 5.) Beweisen oder widerlegen Sie folgende
> Behauptungen.
>
> 1. [mm]n \cdot \log(n) \in O(n)[/mm]
> 2. [mm]\lfloor \log(n) \rfloor! \in O(n^{\log(\log(n))})[/mm]
>
> ich habe gerade einige Probleme bei der Landau-Notation und
> zwar muss ich bei 1. zeigen, dass eine superlineare
> Funktion von einer linearen Funktion von oben beschränkt
> werden kann, was meiner Meinung nach falsch wäre.
Ist es auch.
> Somit wäre mein Ansatz [mm]n \cdot \log(n) \notin O(n) \Leftrightarrow \forall n_0 \in \IN, c \in \IR^{+}: \exists n \ge n_0: c \cdot n < n \cdot \log(n)[/mm]
Soweit so gut. Aber jetzt:
> [mm]\Rightarrow c \cdot n < n \cdot \log(n)[/mm]
Jetzt hast du die Quantoren entsorgt. $c$ und $n$ sind nicht mehr definiert, und dieser Ausdruck macht keinen Sinn mehr. Und folgt insb. nicht aus dem was davor steht. Also so darfst du das auf keinen Fall aufschreiben und abgeben!
> [mm]\Leftrightarrow c < \log(n) \Leftrightarrow a^c < n[/mm]
> (die Basis des Logarithmus war beliebig). Aber wie mache
> ich jetzt weiter (Auswahl von einem n und c) und stimmen
> die Schritte bisher?
Frei rechnen kannst du ja schon so. Du siehst: fuer jedes $a$ und $c$ ist $n$ irgendwann groesser als [mm] $a^c$. [/mm]
Du hast $c$ und [mm] $n_0$ [/mm] gegeben. Also waehle $n = [mm] \max\{ n_0, \lceil a^c + 1 \rceil \}$. [/mm] Dann gilt $n [mm] \ge n_0$ [/mm] und $c [mm] \cdot [/mm] n < n [mm] \cdot \log(n)$. [/mm] Damit hast du gezeigt, dass $n [mm] \log [/mm] n [mm] \not\in [/mm] O(n)$ ist.
> zu 2.) Die Klammer steht übrigens für die Gaußklammer,
> also hier gilt [mm]\lfloor \log(n) \rfloor! \in O(n^{\log(\log(n))}) \Leftrightarrow \exists n_0 \in \IN, c \in \IR^+: \forall n \ge n_0: \lfloor \log(n) \rfloor! \le c \cdot n^{\log(\log(n))} \Rightarrow \lfloor \log(n) \rfloor! \le c \cdot n^{\log(\log(n))} \Leftrightarrow \log(\frac{\lfloor \log(n) \rfloor!}{c}) \le \log(\log(n)) \cdot \log(n)[/mm]
> Wie mache ich hier weiter?
Eine hilfreiche Abschaetzung fuer $k!$ ist [mm] $k^k$. [/mm] Damit kannst du [mm] $\lfloor \log [/mm] n [mm] \rfloor!$ [/mm] durch [mm] $(\log n)^{\log n}$ [/mm] abschaetzen (und bist insb. die Gaussklammer los).
Wenn du jetzt den Logarithmus einmal von [mm] $(\log n)^{\log n}$ [/mm] nimmst und dann von [mm] $n^{\log\log n}$ [/mm] bist du ziemlich schnell fertig.
LG Felix
|
|
|
| |
|
Hallo Felix,
danke für deine Antwort.
> > Somit wäre mein Ansatz [mm]n \cdot \log(n) \notin O(n) \Leftrightarrow \forall n_0 \in \IN, c \in \IR^{+}: \exists n \ge n_0: c \cdot n < n \cdot \log(n)[/mm]
>
> Soweit so gut. Aber jetzt:
>
> > [mm]\Rightarrow c \cdot n < n \cdot \log(n)[/mm]
>
> Jetzt hast du die Quantoren entsorgt. [mm]c[/mm] und [mm]n[/mm] sind nicht
> mehr definiert, und dieser Ausdruck macht keinen Sinn mehr.
> Und folgt insb. nicht aus dem was davor steht. Also so
> darfst du das auf keinen Fall aufschreiben und abgeben!
Warum ich habe lediglich die Definition eingesetzt und im hinteren Teil kommt, dann $c [mm] \cdot [/mm] n < n [mm] \cdot \log(n)$ [/mm] vor und definiert wurden $c,n$ nach Definition. In einem Beispiel aus der Übung war es ähnlich.
[mm] $2^n \notin \Omega(3^n) \Leftrightarrow \forall n_0 \in \IN, [/mm] c [mm] \in \IR^+: \exists [/mm] n [mm] \ge n_0: c3^n [/mm] > [mm] 2^n$
[/mm]
[mm] $c3^n [/mm] > [mm] 2^n \Leftrightarrow [/mm] n > [mm] \frac{\log(\frac{1}{c})}{\log(\frac{3}{2})}$. [/mm] Nun setzten wir $n = [mm] max(n_0, \frac{\log(\frac{1}{c})}{\log(\frac{3}{2})} [/mm] + 1)$
> > [mm]\Leftrightarrow c < \log(n) \Leftrightarrow a^c < n[/mm]
> > (die Basis des Logarithmus war beliebig). Aber wie mache
> > ich jetzt weiter (Auswahl von einem n und c) und stimmen
> > die Schritte bisher?
>
> Frei rechnen kannst du ja schon so. Du siehst: fuer jedes [mm]a[/mm]
> und [mm]c[/mm] ist [mm]n[/mm] irgendwann groesser als [mm]a^c[/mm].
>
> Du hast [mm]c[/mm] und [mm]n_0[/mm] gegeben. Also waehle [mm]n = \max\{ n_0, \lceil a^c + 1 \rceil \}[/mm].
> Dann gilt [mm]n \ge n_0[/mm] und [mm]c \cdot n < n \cdot \log(n)[/mm]. Damit
> hast du gezeigt, dass [mm]n \log n \not\in O(n)[/mm] ist.
>
Kannst du mir bitte diesen abschließenden Schritt erklären, also $n = [mm] \max\{ n_0, \lceil a^c + 1 \rceil \}$ [/mm] Ich verstehe, dass $n$ größer sein muss als [mm] $a^c$, [/mm] also wählen wir ein [mm] $a^c [/mm] + 1$ und dass $n [mm] \ge n_0$ [/mm] ist. Ist das die Erklärung für diesen Schritt?
> > zu 2.) Die Klammer steht übrigens für die Gaußklammer,
> > also hier gilt [mm]\lfloor \log(n) \rfloor! \in O(n^{\log(\log(n))}) \Leftrightarrow \exists n_0 \in \IN, c \in \IR^+: \forall n \ge n_0: \lfloor \log(n) \rfloor! \le c \cdot n^{\log(\log(n))} \Rightarrow \lfloor \log(n) \rfloor! \le c \cdot n^{\log(\log(n))} \Leftrightarrow \log(\frac{\lfloor \log(n) \rfloor!}{c}) \le \log(\log(n)) \cdot \log(n)[/mm]
> > Wie mache ich hier weiter?
>
> Eine hilfreiche Abschaetzung fuer [mm]k![/mm] ist [mm]k^k[/mm]. Damit kannst
> du [mm]\lfloor \log n \rfloor![/mm] durch [mm](\log n)^{\log n}[/mm]
> abschaetzen (und bist insb. die Gaussklammer los).
>
> Wenn du jetzt den Logarithmus einmal von [mm](\log n)^{\log n}[/mm]
> nimmst und dann von [mm]n^{\log\log n}[/mm] bist du ziemlich schnell
> fertig.
Ich danke für diesen Abschätzung, also komme ich auf [mm] $\lfloor \log(n) \rfloor! \le [/mm] c [mm] \cdot n^{\log(\log(n))} \Leftrightarrow \lfloor \log(n) \rfloor! \le \log(n)^{\log(n)} \le [/mm] c [mm] n^{\log(\log(n))} \Leftrightarrow \log(\log(n)) \cdot \log(n) \le \log(c) [/mm] + [mm] \log(\log(n)) \cdot \log(n) \Leftrightarrow [/mm] 0 [mm] \le \log(c) \Leftrightarrow [/mm] 1 [mm] \le [/mm] c$
Da $c [mm] \ge [/mm] 1$ gilt dies für alle $n [mm] \in \IN$
[/mm]
Stimmt das, denn ich bin skeptisch und behaupte, dass ich die Abschätzung nicht 100% korrekt eingesetzt habe :)
>
> LG Felix
>
Grüße
Joe
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:38 So 09.12.2012 | | Autor: | felixf |
Moin Joe!
> danke für deine Antwort.
>
> > > Somit wäre mein Ansatz [mm]n \cdot \log(n) \notin O(n) \Leftrightarrow \forall n_0 \in \IN, c \in \IR^{+}: \exists n \ge n_0: c \cdot n < n \cdot \log(n)[/mm]
>
> >
> > Soweit so gut. Aber jetzt:
> >
> > > [mm]\Rightarrow c \cdot n < n \cdot \log(n)[/mm]
> >
> > Jetzt hast du die Quantoren entsorgt. [mm]c[/mm] und [mm]n[/mm] sind nicht
> > mehr definiert, und dieser Ausdruck macht keinen Sinn mehr.
> > Und folgt insb. nicht aus dem was davor steht. Also so
> > darfst du das auf keinen Fall aufschreiben und abgeben!
>
> Warum ich habe lediglich die Definition eingesetzt und im
> hinteren Teil kommt, dann [mm]c \cdot n < n \cdot \log(n)[/mm] vor
> und definiert wurden [mm]c,n[/mm] nach Definition. In einem Beispiel
> aus der Übung war es ähnlich.
Es ist recht wichtig wie genau man es aufschreibt. Und nur weil es in der Uebung so aufgeschrieben wurde heisst noch nicht dass es auch so richtig ist 
> [mm]2^n \notin \Omega(3^n) \Leftrightarrow \forall n_0 \in \IN, c \in \IR^+: \exists n \ge n_0: c3^n > 2^n[/mm]
>
> [mm]c3^n > 2^n \Leftrightarrow n > \frac{\log(\frac{1}{c})}{\log(\frac{3}{2})}[/mm].
> Nun setzten wir [mm]n = max(n_0, \frac{\log(\frac{1}{c})}{\log(\frac{3}{2})} + 1)[/mm]
Das ist der Rechenweg bzw. eine Erlaeuterung, wie man auf den Beweis kommt. Richtig aufschreiben sollte man es dann so:
> Seien [mm] $n_0 \in \IN$ [/mm] gegeben und $c > 0$. Fuer $n := [mm] \max\{ n_0, \frac{\log(1/c)}{\log(3/2)} + 1 \}$
[/mm]
> gilt nun $c [mm] \cdot 3^n [/mm] > [mm] 2^n \Leftrightarrow [/mm] n > [mm] \frac{\log(1/c)}{\log(3/2)}$,
[/mm]
> weshalb fuer dieses $n [mm] \ge n_0$ [/mm] gilt $c [mm] \cdot 3^n [/mm] > [mm] 2^n$. [/mm] Damit
> ist [mm] $2^n \not\in \Omega(3^n)$.
[/mm]
Hieran kann man schlecht nachvollziehen warum man direkt auf dieses $n$ gekommen ist. Deswegen wurde es in der Uebung wohl anders aufgeschrieben :)
> > > [mm]\Leftrightarrow c < \log(n) \Leftrightarrow a^c < n[/mm]
> > > (die Basis des Logarithmus war beliebig). Aber wie mache
> > > ich jetzt weiter (Auswahl von einem n und c) und stimmen
> > > die Schritte bisher?
> >
> > Frei rechnen kannst du ja schon so. Du siehst: fuer jedes [mm]a[/mm]
> > und [mm]c[/mm] ist [mm]n[/mm] irgendwann groesser als [mm]a^c[/mm].
> >
> > Du hast [mm]c[/mm] und [mm]n_0[/mm] gegeben. Also waehle [mm]n = \max\{ n_0, \lceil a^c + 1 \rceil \}[/mm].
> > Dann gilt [mm]n \ge n_0[/mm] und [mm]c \cdot n < n \cdot \log(n)[/mm]. Damit
> > hast du gezeigt, dass [mm]n \log n \not\in O(n)[/mm] ist.
> >
>
> Kannst du mir bitte diesen abschließenden Schritt
> erklären, also [mm]n = \max\{ n_0, \lceil a^c + 1 \rceil \}[/mm]
> Ich verstehe, dass [mm]n[/mm] größer sein muss als [mm]a^c[/mm], also
> wählen wir ein [mm]a^c + 1[/mm] und dass [mm]n \ge n_0[/mm] ist. Ist das die
> Erklärung für diesen Schritt?
Nun, du musst ja ein $n [mm] \ge n_0$ [/mm] angeben, fuer das $c [mm] \cdot [/mm] n < n [mm] \cdot \log [/mm] n$ gilt. Und du hattest gezeigt, dass dies erfuellt ist, wenn $n [mm] \ge a^c [/mm] + 1$ ist.
Diese Wahl $n := [mm] \max\{ n_0, \lceil a^c + 1 \rceil \}$ [/mm] erfuellt nun beide Voraussetzungen ($n [mm] \ge n_0$ [/mm] und $c [mm] \cdot [/mm] n < n [mm] \cdot \log [/mm] n$), womit es zeigt, dass $n [mm] \cdot \log [/mm] n [mm] \not\in [/mm] O(n)$ ist.
> > > zu 2.) Die Klammer steht übrigens für die Gaußklammer,
> > > also hier gilt [mm]\lfloor \log(n) \rfloor! \in O(n^{\log(\log(n))}) \Leftrightarrow \exists n_0 \in \IN, c \in \IR^+: \forall n \ge n_0: \lfloor \log(n) \rfloor! \le c \cdot n^{\log(\log(n))} \Rightarrow \lfloor \log(n) \rfloor! \le c \cdot n^{\log(\log(n))} \Leftrightarrow \log(\frac{\lfloor \log(n) \rfloor!}{c}) \le \log(\log(n)) \cdot \log(n)[/mm]
> > > Wie mache ich hier weiter?
> >
> > Eine hilfreiche Abschaetzung fuer [mm]k![/mm] ist [mm]k^k[/mm]. Damit kannst
> > du [mm]\lfloor \log n \rfloor![/mm] durch [mm](\log n)^{\log n}[/mm]
> > abschaetzen (und bist insb. die Gaussklammer los).
> >
> > Wenn du jetzt den Logarithmus einmal von [mm](\log n)^{\log n}[/mm]
> > nimmst und dann von [mm]n^{\log\log n}[/mm] bist du ziemlich schnell
> > fertig.
>
> Ich danke für diesen Abschätzung, also komme ich auf
> [mm]\lfloor \log(n) \rfloor! \le c \cdot n^{\log(\log(n))} \Leftrightarrow \lfloor \log(n) \rfloor! \le \log(n)^{\log(n)} \le c n^{\log(\log(n))}[/mm]
Das stimmt so, aber aufschreiben darfst du es nicht  Aus [mm] $\lfloor \log(n) \rfloor! \le [/mm] c [mm] \cdot n^{\log(\log(n))}$ [/mm] folgt naemlich nicht, dass [mm] $\log(n)^{\log(n)} \le [/mm] c [mm] n^{\log(\log(n))}$ [/mm] gilt. Es gibt (moeglicherweise) ein paar Werte von $n$, fuer die diese Implikation falsch ist.
> [mm]\Leftrightarrow \log(\log(n)) \cdot \log(n) \le \log(c) + \log(\log(n)) \cdot \log(n) \Leftrightarrow 0 \le \log(c) \Leftrightarrow 1 \le c[/mm]
>
> Da [mm]c \ge 1[/mm] gilt dies für alle [mm]n \in \IN[/mm]
Das ist als Herleitung super. Aber schreib es lieber so auf:
Setze $c := 1$. Dann gilt $c [mm] \cdot \lfloor \log(n) \rfloor! [/mm] = [mm] \lfloor \log(n) \rfloor! \le (\log n)^{\log n} [/mm] = [mm] \exp(\log [/mm] n [mm] \cdot \log\log [/mm] n) = [mm] n^{\log\log n}$. [/mm] Da dies fuer alle $n > 1$ gilt (andernfalls ist [mm] $\log\log [/mm] n$ gar nicht definiert), folgt [mm] $\lfloor \log(n) \rfloor! [/mm] = [mm] O(n^{\log\log n})$.
[/mm]
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:09 Di 11.12.2012 | | Autor: | JoeSunnex |
Hallo Felix,
ich danke dir für deine Ausführungen. Das Thema wurde erst letzte Woche eingeführt und da wurde anscheinend versucht es anschaulich darzustellen und die Formalität daher etwas weiter nach hinten zu schieben :)
Grüße
Joe
|
|
|
|
