Fragen zur Lösung |
| 13.07.2015, 19:46 | -asdfg- | Auf diesen Beitrag antworten » | ||||
| Fragen zur Lösung Hallo, hätte gerne kurz die Lösung zur folgenden Aufgabe besprochen, da hierzu die Musterlösung fehlt. ____________________ Als zweites hätte ich eine kurze Verständnisfrage zu einer Aussage im Skript. Undzwar: Gegeben seien zwei auf den natürlichen Zahlen definierte Funktionen f(n) und g(n), deren Wertemenge im Bereich der positiven reellen Zahlen liege. Es existiere eine natürliche Zahl n0 und eine positive reelle Zahl c, so daß für alle n ? n0 gelte: f(n) ? c * g(n) Dann schreiben wir f(n) = O(g(n)) Nach ein paar Beispielen folgte folgender Satz: Nach der obigen Definition gilt auch f(n) = 10n + 4 = O(n^2) (ursprünglich war es nur O(n) im Beispiel) ! Es wird aber im Rahmen der Algorithmentheorie bei Angaben mittels des Landau-Symbols immer eine möglichst einfache Funktion g(n) gesucht, die das Wachstum von f(n) für große n gut beschreibt, so daß für hinreichend große Zahlen n gilt: f(n) ? c*g(n) Kann mir das einer kurz erklären, warum 10n + 4 auch ein Aufwand von O(n^2) gilt, obwohl es eigentlich linear wächst und der Faktor 10 einen unbedeutenden Unterschied macht? Meine Ideen: Nach meiner Auffassung ist das 1. richtig, da n^2 den mit Abstand größten Unterschied macht und der Rest sich irgendwann nicht mehr sichtbar auswirkt. Beim 2. bin ich mir nicht sicher, weil ich mich da an ein Video erinnere in dem gesagt wurde, dass ein kleineres n in einem größeren Aufwand miteinbegriffen ist (also n ist in einem Aufwand von n^2 enthalten, n^2 ist in einem Aufwand von n^3 mit einbegriffen, etc.). Das dritte ist falsch, der Aufwand ist O(n^3) und nicht O(n) und das 4. ist richtig. Raus kommt 8n*4log(n) und die Konstanten wirken sich bei einem ausreichend großen n kaum auf das Ergebnis aus. |
||||||
| 13.07.2015, 19:47 | -asdfg- | Auf diesen Beitrag antworten » | ||||
Korrektur: Beim 3. ist der Aufwand O(n^2) |
||||||
| 13.07.2015, 19:58 | Captain Kirk | Auf diesen Beitrag antworten » | ||||
Hallo, es gilt 10n+4=O(n) und es gilt 10n+4=O(n²) in beiden Fällen lässen sich geeignete und C finden. (z.B. 10 und 2)
Worauf bezieht sich das? |
||||||
| 13.07.2015, 23:59 | -asdfg- | Auf diesen Beitrag antworten » | ||||
Hallo, danke schonmal. Ich bezog mich eigentlich auf den Anhang, der scheinbar nicht geuploadet wurde. Die 4 Gleichungen, von denen man sagen soll ob sie stimmen oder nicht waren: 1. 3n²+7n+12=O(n²) 2. n²=O(n³) 3. (n²+1)/n=O(n) 4. 3n+5n*ld(n^4) = O(n*log(n)) Und dazu meine Ideen: Nach meiner Auffassung ist das 1. richtig, da n^2 den mit Abstand größten Unterschied macht und der Rest sich irgendwann nicht mehr sichtbar auswirkt. Beim 2. bin ich mir nicht sicher, weil ich mich da an ein Video erinnere in dem gesagt wurde, dass ein kleineres n in einem größeren Aufwand miteinbegriffen ist (also n ist in einem Aufwand von n^2 enthalten, n^2 ist in einem Aufwand von n^3 mit einbegriffen, etc.). Das dritte ist falsch, der Aufwand ist O(n^2) und nicht O(n) da n³/n = n² ergibt (die 1 wird bei großen n irrelevant) und das 4. ist richtig. Raus kommt 8n*4log(n) und die Konstanten wirken sich bei einem ausreichend großen n kaum auf das Ergebnis aus. |
||||||
| 14.07.2015, 00:45 | Captain Kirk | Auf diesen Beitrag antworten » | ||||
Du hast eine Definition des Begriffs. Anhand dessen kann man zeigen ob die Aussagen stimmen oder nicht, wie ich bereits in einem Fall gemacht habe. Das sollst du auch hier erledigen. P.S. Deine Argumentation zu 3. passt nicht zur Aufgabe. Bitte überprüfe deine Posts, insbesondere Die Aufgabenstellungen auf Tippfehler (siehe auch den ersten Post). Es gibt unter dem Eingabefeld einen Vorschau-Knopf. Und
|
||||||
| 14.07.2015, 12:32 | -asdfg- | Auf diesen Beitrag antworten » | ||||
Ah, ok. Ich nehme an, ich bestimme einfach den Grenzwert? Der Grenzwert von Nr. 1 geht gegen 3. 3n²+7n+12=O(n²) ? => lim (n -> oo) (3n²+7n+12)/n² = 3. Somit ist die Aussage 3n²+7n+12=O(n²) wahr. Nr. 2 n²=O(n³)? => lim (n -> oo) n²/n³ = 0 Somit ist die Aussage n²=O(n³) falsch. Nr 3. (n³+1)/n=O(n)? (Tippfehler korrigiert) lim (n -> oo) ((n³+1)/n)/n = (n³+1)/n² = oo Somit ist die Aussage (n³+1)/n=O(n) wahr. Nr 4. 3n+5n*ld(n^4)=O(n*log(n)) ? => 3n+5n*ld(n^4) = 3n+5n*4*ld(n) = 3n+20n*log(n) 3n+20n*log(n)=O(n*log(n)) ? lim (n -> oo) (3n+20n*log(n))/n*log(n) = 20 Somit ist 3n+5n*ld(n^4)=O(n*log(n)) wahr. Was sagt ihr dazu? |
||||||
| Anzeige | ||||||
|
|
||||||
| 14.07.2015, 15:32 | Captain Kirk | Auf diesen Beitrag antworten » | ||||
Du hast im ersten Post eine Definition hingeschrieben. Bitte verwende die doch und nicht irgendwas halbgares anderes. Wenn du eine äquivalente Def. verwenden willst dann sag es bitte, und verwende auch eine wirklich äquivalente Definition. Und ich habe ja auch bereits ein Beispiel gemacht. Scheinbar überliest du das nach wie vor konsequent.
Deine Schlußfolgerungen sind kaum nachvollziehbar und mitunter falsch. |
||||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
| Die Neuesten » |
|
