Beweis O-Notation < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 19:51 Sa 02.06.2007 | | Autor: | RalU |
| Aufgabe | Hallo, Leute!
Es geht um folgende Aufgabe (O-notation, Komplexitätsklassen):
Beweisen oder widerlegen Sie folgende Behauptung:
[mm] 5n^{2}+100n [/mm] = [mm] O(n^{2}) [/mm] |
Ok, ich hab folgendermaßen angesetzt:
[mm] \exists [/mm] c > 0, [mm] \exists [/mm] no [mm] \in \IN \forall [/mm] n > no gilt:
f(n) <= c*g(n)
Beweisidee:
wähle c=5
wähle no=1
jetzt folgt
f(no) <= c* g(n0)
also
[mm] no^{2}+100*no<= 1*n^{2}
[/mm]
101<=5 -> falsch
Damit wäre die Aussage widerlegt.
Aber eigentlich bin ich mir da nicht sicher, weil ich denke, die Aussage ist gültig. Aber wo liegt dann mein Fehler?
Mit freundlichen Grüßen,
Ralf
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:20 Di 12.06.2007 | | Autor: | HohesC |
Ist die Frage noch aktuell oder hat sich das mittlerweile erledigt? Die Fälligkeit ist ja abgelaufen...
|
|
|
| |
|
> Hallo, Leute!
> Es geht um folgende Aufgabe (O-notation,
> Komplexitätsklassen):
>
> Beweisen oder widerlegen Sie folgende Behauptung:
> [mm]5n^{2}+100n[/mm] = [mm]O(n^{2})[/mm]
> Ok, ich hab folgendermaßen angesetzt:
>
> [mm]\exists[/mm] c > 0, [mm]\exists[/mm] no [mm]\in \IN \forall[/mm] n > no gilt:
>
> f(n) <= c*g(n)
>
>
> Beweisidee:
> wähle c=5
> wähle no=1
>
> jetzt folgt
>
> f(no) <= c* g(n0)
> also
> [mm]no^{2}+100*no<= 1*n^{2}[/mm]
> 101<=5 -> falsch
>
>
> Damit wäre die Aussage widerlegt.
> Aber eigentlich bin ich mir da nicht sicher, weil ich
> denke, die Aussage ist gültig. Aber wo liegt dann mein
> Fehler?
>
> Mit freundlichen Grüßen,
> Ralf
falls es noch von Belangen ist:
Mein Lösungsvorschlag :
5* [mm] n^{2} [/mm] + 100*n [mm] \le c*n^{2} [/mm] dividiere durch [mm] n^{2}
[/mm]
5+ [mm] \bruch{100}{n} \le [/mm] c
man sieht hier, das der Term [mm] \bruch{100}{n} [/mm] bei n [mm] \to \infty [/mm] gegen 0 geht.
daraus folgt, c [mm] \ge [/mm] 105
nun wählen wir ein [mm] n_{0} [/mm] = 1 , c = 105 und setzen dies ein
5* [mm] 1^{2} [/mm] + 100*1 [mm] \le [/mm] 105*1
105 [mm] \ge [/mm] 105 =>passt und gilt auch [mm] \forall [/mm] n [mm] \ge n_{0}
[/mm]
lg
|
|
|
|
