O-Notation Beweise < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Seien k,d [mm] \in \IN [/mm] beliebig aber fest. Beweise:
(7) [mm] n^n \in O(2^{n^2})
[/mm]
(8) [mm] log^k [/mm] n [mm] \in O(\wurzel{n}) [/mm] |
Hallo liebe Leute,
finde diese Aufgaben sehr schwer, inbs. die (8). Wäre super, wenn mir jemand weiterhelfen könnte. Freue mich über jede Antwort!
Liebe Grüße, Janine
P.S. Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo Janine,
schreib doch als erstes immer hin, was zu zeigen ist, strikt nach Definition.
Sei mal der log zur Basis 2, dann ist doch bei (8) zu zeigen: Es gibt [mm] n_0 [/mm] und c >0 so dass für alle [mm] n\geq n_0
[/mm]
[mm] \log^k(n)\leq \:\: c\cdot \sqrt{n}
[/mm]
Wir quadrieren beide Seiten:
[mm] \log^{2k} (n)\leq\:\: c^2\cdot [/mm] n
Wir nehmen ''2 hoch'':
[mm] n^{2k} \leq \cdot 2^{c^2\cdot n}
[/mm]
Setzen wir mal c=1 an - d.h. probieren wir, ob es mit diesem c klappt, ein [mm] n_0 [/mm] zu finden:
[mm] n^{2k}\leq 2^n
[/mm]
Für [mm] n_0 [/mm] =1 gilt diese Ungl. schon mal. Können wir -zB durch Induktion nach n- zeigen, dass sie dann auch für alle
[mm] n\geq n_0 [/mm] =1 gilt ?
Probieren wir's:
Gelte es für n, zzg:
[mm] (n+1)^{2k}\leq 2^{n+1}
[/mm]
Es ist [mm] (n+1)^{2k} [/mm] = [mm] n^{2k} [/mm] + [mm] \sum_{j=0}^{2k-1} \vektor{2k\\ j}\cdot n^j\leq n^{2k}+\vektor{2k\\k}\cdot n^{2k-1}\cdot [/mm] (2k-1)
Wenn wir also noch Induktion nach k machen, es in diesem Ind.Schritt für 2k-1 voraussetzen und als [mm] n_0 [/mm] nicht 1, sondern
[mm] (2k-1)\cdot \vektor{2k\\k} [/mm]
wählen, sollt es hinkommen.
Ich hoff, hier ist vor allem die Vorgehensweise etwas deutlich geworden.
Viele Grüße, viel Erfolg !
Mathias
|
|
|
| |
|
Hey Mathias,
vielen Dank für deine ausführliche Antwort!! Mit deiner Vorgehensweise komme ich super zurecht - es hilft mir auch sehr diesen "Einführungssatz" immer oben drüber zu schreiben!
Allerdings bin ich mit dem Induktionsbeweis überfordert. Frage mich, ob es nicht auch irgendwie einfacher (intuitiver) möglich ist, zu beweisen, dass $ [mm] n^{2k}\leq 2^n [/mm] $. Für [mm] n_0=1 [/mm] gilt die Ungleichung ja. Ich weiss, eine naive Frage, aber warum können wir jetzt nicht einfach sagen: wir wählen also [mm] n_0=1 [/mm] und der Beweis ist erbracht (...)? Weil es gilt doch [mm] n>=n_0.
[/mm]
LG Janine
|
|
|
| |
|
Moin Janine,
nun, so einfach geht es leider nicht, denn wir müssen ja zeigen, dass es für alle [mm] n\geq n_0 [/mm] gilt.
Ok, Du möchtest zeigen, dass es für alle [mm] k\in\IN [/mm] ein [mm] n_0=n_0(k) [/mm] gibt, so dass für alle [mm] n\geq n_0 [/mm] gilt: [mm] n^{2k}\leq 2^n.
[/mm]
Machen wir es ganz zu Fuss und zeigen zunächst:
Für [mm] k\geq [/mm] 7 gilt [mm] 2k^2\leq 2^k. \:\: (\star)
[/mm]
k=7: Stimmt.
[mm] k\rightarrow [/mm] k+1: Es ist [mm] 2(k+1)^2=2k^2+2\cdot (2k+1)\leq 2k^2+2k^k\leq 2^k+2^k=2^{k+1}.
[/mm]
Nun zeigen wir: Für [mm] n\geq 2^k [/mm] (und [mm] k\geq [/mm] 7) gilt [mm] n^{2k}\leq 2^n.
[/mm]
[mm] n=2^k: [/mm] Dann ist
Linke Seite = [mm] n^{2k}=2^{2k^2}
[/mm]
Rechte Seite = [mm] 2^{2^k} [/mm] und damit stimmt's wg. der Aussage [mm] (\star).
[/mm]
Induktionsschritt:
[mm] (n+1)^2k=n^{2k} +\sum_{j=0}^{2k-1}\vektor{2k\\j}\cdot n^j\leq n^{2k}+2k\cdot \vektor{2k\\k}\cdot n^{2k-1}
[/mm]
und dies lässt sich für [mm] n\geq n_0=2k\cdot \vektor{2k\\k} [/mm] nach oben gegen [mm] n^{2k}+n^{2k}\leq 2\cdot 2^n=2^{n+1} [/mm] abschätzen.
Sicher geht all das noch anders und viel eleganter, via taylor-Entwicklung und so, aber so elementar geht's halt auch.
Viele Grüße,
Mathias
|
|
|
| |
|
Hey Mathias,
ich habe Probleme folgende Zeile zu verstehen. Klar, dass du "ganz links" k+1 einsetzt, aber dann...
Es ist $ [mm] 2(k+1)^2=2k^2+2\cdot(2k+1)\leq 2k^2+2k^k\leq 2^k+2^k=2^{k+1}. [/mm] $
Dass [mm] 2(k+1)^2=2k^2+2\cdot(2k+1) [/mm] ist mir klar. Aber der Rest dahinter... Wieso ist $ [mm] 2^k+2^k=2^{k+1} [/mm] $? Muss es nicht $ [mm] 2^k [/mm] + [mm] 2^k [/mm] = [mm] 2\cdot2^k [/mm] $ heissen? Bin ich doof?
Und wo ich gerade dabei bin: du führst die Ungleichung (*) ein $ [mm] 2k^2\leq 2^k. \:\: (\star) [/mm] $. Mir ist klar, dass dies sinvoll ist für die spätere Verwendung, aber: wie kommt man darauf? k=7 ist einfach beliebig gewählt, richtig?
Ich will das unbedingt verstehen!!!!
LG Janine
|
|
|
| |
|
Hallo Janine,
also ich hab halt versucht, das zu beweisen, via Induktion.
Wenn ich [mm] n^{2k} \leq 2^n [/mm] durch Induktion zeigen will, so krieg ich
[mm] (n+1)^{2k}=n^{2k}+\sum_{j=0}^{2k-1}\vektor{2k\\j}\cdot n^j
[/mm]
[mm] \leq n^{2k} [/mm] + [mm] 2k\cdot n^{2k-1}\cdot \max\{\vektor{2k\\j},\: j=0,\ldots , 2k-1\} [/mm] =
= [mm] n^{2k} [/mm] + [mm] 2k\cdot n^{2k-1}\cdot \vektor{2k\\k}
[/mm]
Nach Ind. Annahme gilt dabei dann ja [mm] n^{2k}\leq 2^n,
[/mm]
und es ist [mm] 2^{n+1}=2\cdot 2^n, [/mm] also wäre es ja an der Stelle hilfeich, wenn wir zeigen könnten, daß
[mm] 2k\cdot n^{2k-1}\cdot \vektor{2k\\k}\:\:\leq\:\: 2^n [/mm] gilt,
daher kommt man auf die Wahl des [mm] n_0.
[/mm]
Und dann seh ich gerade: das mit der Aussage úber k für [mm] k\geq [/mm] 7 braucht man an der Stelle gar nicht. Arghh !
Na ja, niemand ist perfekt. 
Jedenfalls ist die Vorgehensweise so, dass man erstmal versucht, es durch Induktion zu zeigen, und dann sieht man bei der Rechnung
halt, was man noch so braucht (wie zB hier das [mm] n_0). [/mm] Das fällt keinesfalls vom himmel, und auch ist es nicht so, dass man das direkt sieht,
wie man [mm] n_0 [/mm] wählen muss und so.
Viele Gruesse,
Mathias
|
|
|
| |
|
Hi Mathias,
du bist echt eine große Hilfe! Ich glaube, sehr bald hab ichs verstanden!
Kannst du mir sagen, warum die erste Summe von $j=0$ bis $2k-1$ läuft und nicht bis $2k$?
Gruß
|
|
|
|
