O Kalkül |
| 20.04.2013, 17:32 | ThalesVonMilet | Auf diesen Beitrag antworten » | ||
| O Kalkül Ich habe mich jetzt schon ein wenig mit den Landau Symbolen auseinandergesetzt und habe jetzt noch eine Frage 
Ich muss beweisen oder widerlegen: n = O(n^1/2) Ist es richtig, dass ich beweisen muss: f(n) <= c * g(n) wobei f(n) = n und g(n) = n^1/2 Danke schonmal für eure Antworten ;P |
||||
| 20.04.2013, 19:04 | weisbrot | Auf diesen Beitrag antworten » | ||
RE: O Kalkül
lg |
||||
| 20.04.2013, 20:00 | ThalesVonMilet | Auf diesen Beitrag antworten » | ||
Ahh, alles klar danke
Demnach ist die Aussage falsch, da c ja, um die Bedingung zu erfüllen, größer als n^1/2 sein muss. Aber irgendwann holt n ja c ein und dann stimmts nichmehr. --> So stimmt das oder ? XD Danke nochma ;P |
||||
| 20.04.2013, 20:06 | weisbrot | Auf diesen Beitrag antworten » | ||
nein, das c muss unabhängig von n sein - guck dir die definition genau an. lg |
||||
| 20.04.2013, 20:50 | ThalesVonMilet | Auf diesen Beitrag antworten » | ||
Jo, aber wenn ich jetzt c, unabhängig von n, auf 5 setze, dann dann ist es ja nur bis n = 5 richtig. Für n = 6 passt es ja dann nicht mehr. Wähle ich jetzt ma ein anderes c, wird es immer solange stimmen bis n = c + 1. Oder? :P Das heißt, dass bei n = unendlich : c = unendlich + 1 mindestens sein muss. Und das funzt ja nich so gut XD Danke für deine Antwort:-) |
||||
| 20.04.2013, 20:59 | weisbrot | Auf diesen Beitrag antworten » | ||
es geht aber schon noch um und - entsprechend solltest du deine beispielwerte etwas anpassen. aber es stimmt: für jedes feste c stimmt die ungleichung irgendwann nicht mehr - das gilt es dann nur noch etwas formaler zu beweisen. lg |
||||
| Anzeige | ||||
|
|
||||
| 21.04.2013, 08:33 | ThalesVonMilet | Auf diesen Beitrag antworten » | ||
Ja, da oben hab ich eindeutig %^$*+£ geschrieben. Es muss also im Beispiel n = 5 heißen, dass c >= 5^ 1/2 sein muss. Und allgemein formuliert steht dann n <= c * n^1/2, c >= n^1/2 Wie kann ich das jetzt noch verallgemeinern, bzw. widerlegen oder beweisen ? Muss ich das vielleicht mittels vollständiger Induktion machen oder macht man das anders? Hab echt kein Plan xD |
||||
| 21.04.2013, 15:35 | weisbrot | Auf diesen Beitrag antworten » | ||
jaaa.. wie man eben so beweise führt. vollständige induktion funktioniert hier aber nicht, da du ja keine aussage der form "für alle n aus IN gilt: ..." hast. aber du bist doch schon fast am ziel - wenn man annimmt, dass ein solches c existiert, dann (hast du gezeigt) müsste für alle n ab einem bestimmten n_0 sein. dass/warum es so eine reelle zahl (wie gesagt konstant, unabhängig von n) niemals geben kann kannst du dir sicher selbst überlegen. lg |
||||
| 21.04.2013, 16:22 | ThalesVonMilet | Auf diesen Beitrag antworten » | ||
Naja, wenn n unendlich groß ist, müsste c ja wurzel unendlich und größer sein. Wurzel unendlich ist ja unendlich und größer geht ja nicht. Stimmt das so, anders kann ichs mir nich erklären^^ Es ist klar, dass es so ein c nicht geben kann, da f(x) ab einem Punkt wieder größer ist, aber wie kann ich das formulieren? |
||||
| 21.04.2013, 18:12 | weisbrot | Auf diesen Beitrag antworten » | ||
naja, nur dass "unendlich" keine reelle zahl ist.. mathematisch korrekt würde man sagen, dass nach oben unbeschränkt ist, d.h. genau: es gibt keine zahl c, sodass für alle n; bzw.: für alle c ist irgendwann (für irgendein n) . und das ist eben genau die negation deiner aussage. lg |
||||
| 21.04.2013, 20:09 | ThalesVonMilet | Auf diesen Beitrag antworten » | ||
Ahh, alles klar ;P Vielen vielen Dank für deine Hilfe ;-) |
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|