Landau-Symbole: Warum ist n^2 + n Element von O(n^2) |
21.05.2010, 10:52 | Gefahrensucher | Auf diesen Beitrag antworten » |
Landau-Symbole: Warum ist n^2 + n Element von O(n^2) Hallo Ich bin gerade über die Definition der Landau-Symbole gestolpert. Wobei ich eigentlich sofort beim ersten hängen geblieben bin. Dort wird folgendes definiert: Da ich noch aus meinen Algorithmen-Vorlesungszeiten weiss, hat mein Prof z.B. bei n^2 + n gesagt, es ist in O(n^2) enthalten. Irgendwie kam mir das jetzt spanisch vor und wollte es mal anhand der Definition nachprüfen. Und das habe ich versucht wie folgt zu tun: Meine Ideen: Wenn f(n) = n^2 + n ist und f(n) Element von O(n^2) sein sollte, müsste die Definition oben ja korrekt sein. Das würde bedeuten, das es eine Konstante C gibt die für ein n>=n0 die Gleichung |f(n)| <= C |g(n)| erfüllt. Jetzt war ich versucht diese Konstante zu ermitteln, wobei ich natürlich auf die Gleichung n^2 + n = C * n^2 gestossen bin. Wenn ich das umforme, komme ich auf C >= 1 + 1/n Das heisst, es gibt keine Konstante, da diese von n abhängen würde => Widerspruch. Somit kann n^2 + n nicht Element von O(n^2) sein. Nun ist meine verwunderte Frage, wo habe ich meinen Denkfehler? Lieben Gruß Euer Gefahrensucher ;-) |
||
21.05.2010, 11:07 | kiste | Auf diesen Beitrag antworten » |
Wähle C=2, so ist dies für jedes n erfüllt. |
||
21.05.2010, 15:21 | Gefahrensucher | Auf diesen Beitrag antworten » |
Da steht man direkt davor und sieht es nicht... Dank Dir |
|
Verwandte Themen
Die Beliebtesten » |
Die Größten » |
|
Die Neuesten » |
|