Beweise Ist fn:=n fuer alle... < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
Hallo, erstmal entschuldigt bitte, dass ich mich an euch wende, aber ich schaue schon zwei Tage auf diese wohl sehr einfache Aufgabe, finde in meinen Gehirnwindungen aber keine Lösung.
Die Aufgabe lautet: Ist fn:= n für alle n aus den natürlichen Zahlen,
so ist f aus [mm] O(n^k) [/mm] für alle k größer gleich 2.
Mir ist klar, dass dies der Fall ist. Ich verstehe nur nicht wie ich den allgemeingültigen Beweis angehe. Falls ihr mir helfen könnt würde ich mich sehr freuen.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo,
es ist per definitionem
[mm] O(n^k)=\{f\colon\IN\to\IN\: |\: \exists c>0\: \exists n_0\in\IN\:\forall n\geq n_0\:\: f(n)\leq c\cdot n^k\}
[/mm]
Du willst zeigen, dass f(n):=n in dieser Klasse liegt, musst also ein c und ein [mm] n_0 [/mm] mit diesen Eigenschaften angeben.
Wähle c=1 und [mm] n_0=1, [/mm] dann musst Du zeigen, dass diese Wahl ''klappt'', also dass fuer alle [mm] n\in\IN, n\geq [/mm] 1 gilt : [mm] n\leq n^k.
[/mm]
Das solltest Du schaffen, oder ?
Viel Erfolg wünscht
Mathias
|
|
|
| |
|
Muss ich mich jetzt schämen, dass ich immernoch total auf dem Schlauch stehe?
Ich habe mir den Post jetzt oft angeschaut und die Antwort studiert. Warum es bei mir nicht klick macht weiß ich auch nicht. Wie mache ich mir den Sachverhalt nun begreiflich? was mach ich nur falsch im Umgang mit Mathematik... hmm
|
|
|
| |
|
Kannst du mit dieser analogen Definition mehr anfangen?
Sei $f [mm] \in [/mm] O(g)$ wenn gilt:
$0 [mm] \le \limes_{x\rightarrow\infty} \sup |\bruch{f(x)}{g(x)}| [/mm] < [mm] \infty$
[/mm]
In deinem Fall mit $f(x) = x$ und $g(x) = [mm] x^k$ [/mm] (wobei $k [mm] \ge [/mm] 1$ )
Falls es dir nicht ganz klar geworden ist, die O-notation bedeutet nur was die obere Schranke ist.
|
|
|
|
