Landau Beweise

10.04.2017, 18:39	Oggel	Auf diesen Beitrag antworten »
Landau Beweise Hi Leute, ich benötige Hilfe bei folgender Aufgabe: Ich fange erstmal mit a an: Hier muss ich ja folgendes zeigen: $\begin{eqnarray} n(n-1) \le c * \sqrt(n^5) \end{eqnarray}$ $\begin{eqnarray} \Leftrightarrow n * (n-1) \le c * n * \sqrt(n^3) \end{eqnarray}$ $\begin{eqnarray} \Leftrightarrow n-1 \le c * \sqrt(n^3) \end{eqnarray*}$ Ist das soweit richtig? Jetzt sieht man doch schon, dass die Gleichung gilt oder? Also gibt es für alle n > 0 ein c >0 für das die Gleichung gilt. Danke schonmal
11.04.2017, 04:06	RipHarambe	Auf diesen Beitrag antworten »
Machst du so brudi: $\begin{eqnarray} n-1 \leq n \leq c \sqrt{nn^2} \Leftrightarrow <br /> 1 \leq c \sqrt{n} \end{eqnarray*}$ kgV: Latex korrigiert
11.04.2017, 10:22	Oggel	Auf diesen Beitrag antworten »
ahh okay danke und das heißt ja, dass es für alle $\begin{eqnarray} n \ge 0 \end{eqnarray}$ ein $\begin{eqnarray} c > 0 \end{eqnarray}$ gibt, sodass die Ungleichung erfüllt ist oder? für b habe ich folgendes: $\begin{eqnarray} \sqrt{n^5} \le c (n(n-1)) \end{eqnarray}$ $\begin{eqnarray} \Leftrightarrow \sqrt{n^2 n^2 * n} \le c * n^2 - cn \end{eqnarray}$ $\begin{eqnarray} \Leftrightarrow n \sqrt{n} \le cn - c \end{eqnarray}$ $\begin{eqnarray} \Leftrightarrow n \sqrt{n} \le c * (n-1) \end{eqnarray}$ und da gilt: $\begin{eqnarray} (n-1) * \sqrt{n} \le n\sqrt{n} \le c (n-1) \end{eqnarray}$ . Das heißt es muss gelten $\begin{eqnarray} \sqrt{n} \le c \end{eqnarray}$ . Da jetzt c von n abhängig ist gilt nicht: $\begin{eqnarray} f_1 \in O(f_2) \end{eqnarray*}$ Kommt das so hin?
12.04.2017, 04:49	RipHarambe	Auf diesen Beitrag antworten »
Zunächst solltest du die Aussage negieren. Sprich (salopp): egal wie du c wählst die Funktion links der Ungleichung wird die Funktion rechts stehts übertreffen. Dann kannst du deine Umformungen übernehmen und musst lediglich das Ungleichungszeichen umdrehen. Zu guter letzt ist die Abschätzug: $\begin{eqnarray} n \sqrt{n} \geq c * n \geq c * (n-1) \end{eqnarray*}$ Zielführend. Unter Erwähnung der strengen Monotonie der Wurzelfunktion folgt die Gültigkeit der Ungleichung. Vorsichtig must du bei n=0 sein. Für diesen Fall darf man das n nicht kürzen, denn durch 0 darf man bekannterweise nicht teilen. Da die Betrachtungen sowieso alle asymptotisch sind ist das aber egal... Sprich die Ungleichung muss erst ab einem gewissen N gelten. Deine Argumentation nach den Umformungen kann ich nicht nachvollziehen
12.04.2017, 08:56	Oggel	Auf diesen Beitrag antworten »
Mhhh aber wenn ich die Ungleichung negiere muss doch auf jeder Seite noch mit -1 multipliziert werden oder? Das hast du in deiner letzten Abschätzung nicht drin Also müsste doch in meiner letzten Umformung stehen: $\begin{eqnarray} -1 (n\sqrt{n}) \ge -1 (c(n-1)) \end{eqnarray}$ Ich meinte mit meiner Argumentation das so, dass man kein $\begin{eqnarray} n_0 \end{eqnarray}$ finden kann sodass es für alle $\begin{eqnarray} n > n_0 \end{eqnarray}$ ein c gibt, sodass die Ungleichung gilt. Da $\begin{eqnarray} c \ge \sqrt{n} \end{eqnarray}$ . Anders ausgedrückt muss man für jedes n ein neues c wählen und zwar mindestes $\begin{eqnarray} \sqrt{n} \end{eqnarray}$
12.04.2017, 10:18	HAL 9000	Auf diesen Beitrag antworten »
Irgendwie kommt einem das hoch kompliziert vor, wenn man das bei dir liest. Es geht doch z.B. bei b) einfach um das Verhalten von $\begin{align} \frac{f_1(n)}{f_2(n)} \end{align}$ für $\begin{align} n\to \infty \end{align}$ , d.h., bleibt es beschränkt oder nicht. Einfach einsetzen: $\begin{align} \frac{f_1(n)}{f_2(n)} = \frac{n^2\sqrt{n}}{n(n-1)} = \frac{\sqrt{n}}{1-\frac{1}{n}} \to \infty \end{align}$ für $\begin{align} n\to\infty \end{align}$ , d.h. unbeschränkt und damit $\begin{align} f_1 \not\in \mathcal{O}(f_2) \end{align}$ .
Anzeige

12.04.2017, 20:37	Oggel	Auf diesen Beitrag antworten »
Stimmt wenn man das so sieht, sieht das viel einfacher aus c und d habe ich mit meinen Kommilitonen schon gelöst. Danke euch

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »