O-Notation/Abschätzung < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | | Es sei f(n) = [mm] n^{3} [/mm] + a [mm] n^{2} [/mm] + b n + d, a,b,d > 0. Beweise mit der Definion von O(g), Omega(g) (ohne Verwendung vom lim), dass f(n) = [mm] Teta(n^{3}) [/mm] ist. Gebe abhängig von a,b,d die passenden Konstanten c, [mm] n_{0} [/mm] für die jeweilige Richtung an. |
Hallo,
ich hab Probleme bei der Aufgabe, weil ich nicht weiß, wie ich genau die Konstanten wählen soll in Abhängigkeit von a,b,d.
Ich hab erstmal folgendes gemacht:
Die Definiton von O(g): O(g) = {f | es gibt ein c > 0, [mm] n_{0} \in \IN: [/mm] f(n) [mm] \le [/mm] c g(n) für alle n [mm] \ge n_{0}}
[/mm]
Definition von Omega(g): Omega(g) = {f| es gibt ein c > 0, [mm] n_{0} [/mm] \ in [mm] \IN: [/mm] f(n) [mm] \ge [/mm] c g(n) für alle n [mm] \ge n_{0}}
[/mm]
Teta(g) = O(g) [mm] \cap [/mm] Omega(g)
D.h., um Teta zu zeigen, muss die Bedingung von O(g) und Omega(g) gelten.
f(n) = O(g) wenn f(n) [mm] \le [/mm] c g(n), [mm] n^{3} [/mm] + a [mm] n^{2} [/mm] + b n + d [mm] \le [/mm] c [mm] n^{3}
[/mm]
Ich hab das c mal so gewählt: c = a +b+ d
Ist das so richtig? Oder wie kann man so ein c in Abhängigkeit von a,b,d wählen? Ich weiß nicht, wie man das am besten machen soll.
Das [mm] n_{0} [/mm] soll auch in Abhängigkeit von a, b, d sein oder? Wenn ich das c so gewählt hab, dann stimmt die Ungleichung schon für [mm] n_{0} [/mm] = 2
Ich weiß leider nicht, wie ich auch das [mm] n_{0} [/mm] in Abh. von a,b, d wählen soll.
Für f(n) = Omega(g) : f(n) [mm] \ge [/mm] c g(n)
[mm] n^{3} [/mm] + a [mm] n^{2} [/mm] + b n + d [mm] \ge [/mm] c [mm] n^{3}
[/mm]
Das c muss doch zwischen 0 und 1 gewählt werden oder? Aber welchen Bruch kann ich denn angeben mit a,b,c? Und hier hab ich auch Probleme mit der Wahl von [mm] n_{0}.
[/mm]
Ich weiß nicht genau, wie ich so was abschätzen soll in Abh. von Variablen.
Ich hoffe, es hilft mir jemand weiter.
Vielen Dank und schönen Abend,
wetterfrosch
|
|
| |
|
Hallo und guten Morgen,
> f(n) = O(g) wenn f(n) [mm]\le[/mm] c g(n), [mm]n^{3}[/mm] + a [mm]n^{2}[/mm] + b n +
> d [mm]\le[/mm] c [mm]n^{3}[/mm]
> Ich hab das c mal so gewählt: c = a +b+ d
> Ist das so richtig? Oder wie kann man so ein c in
> Abhängigkeit von a,b,d wählen? Ich weiß nicht, wie man das
> am besten machen soll.
Ja, ist doch gut !
>
> Das [mm]n_{0}[/mm] soll auch in Abhängigkeit von a, b, d sein oder?
> Wenn ich das c so gewählt hab, dann stimmt die Ungleichung
> schon für [mm]n_{0}[/mm] = 2
> Ich weiß leider nicht, wie ich auch das [mm]n_{0}[/mm] in Abh. von
> a,b, d wählen soll.
Zeig halt nur, dass es für alle [mm] n\geq [/mm] 2 gilt. Das ist's dann auch schon.
>
> Für f(n) = Omega(g) : f(n) [mm]\ge[/mm] c g(n)
> [mm]n^{3}[/mm] + a [mm]n^{2}[/mm] + b n +
> d [mm]\ge[/mm] c [mm]n^{3}[/mm]
>
> Das c muss doch zwischen 0 und 1 gewählt werden oder? Aber
> welchen Bruch kann ich denn angeben mit a,b,c? Und hier hab
> ich auch Probleme mit der Wahl von [mm]n_{0}.[/mm]
>
In dem Bruch müssen a, b usw nicht vorkommen, zu zeigen ist nur, dass es solches c gibt
(nirgendwo steht, dass es aus dem Bereich [0,1] oder so sein muss, lediglich c>0 ist verlangt.
Die Einschränkung [mm] c\in [/mm] [0,1] ergäbe auch einen anderen [mm] \Omega [/mm] - Begriff, denn dann wäre zB
[mm] 10^{19}\cdot n^3 [/mm] nicht mehr in [mm] \Omega (n^3) [/mm] - ist es aber nach geltender Def. 
Wähl doch zB [mm] c=\min{a,b,d\} [/mm] oder so. Zeig aber, dass es mit der Wahl klappt.
> Ich weiß nicht genau, wie ich so was abschätzen soll in
> Abh. von Variablen.
> Ich hoffe, es hilft mir jemand weiter.
>
> Vielen Dank und schönen Abend,
> wetterfrosch
Einen schönen Tag,
Mathias
|
|
|
| |
|
Hallo Mathias,
vielen Dank für deine Antwort. Jetzt weiß ich, dass ich nicht ganz daneben lag mit meiner Wahl :)
Ich weiß bei dem O(g) nicht, wie ich das für alle n [mm] \ge [/mm] 2 zeigen soll. Außerdem soll das laut Angabe auch in Abhängigkeit von a,b und d sein oder? Oder soll das nur für das c gelten? Ich weiß nicht, wie ich das zeigen soll formal. Ich hab mal einfach ein paar Werte eingesetzt für n und gesehen, dass die Ungleichung [mm] n^{3} [/mm] + a [mm] n^{2} [/mm] + b n + d [mm] \le [/mm] (a+b+d) [mm] n^{3} [/mm] schon für alle n [mm] \ge [/mm] 2 gilt. Aber wie zeigt man so was?
Für die andere Richtung f(n) = Omega(g) hab ich das gemacht:
Es soll sein [mm] n^{3} [/mm] + a [mm] n^{2} [/mm] + b n + d [mm] \ge [/mm] c [mm] n^{3}
[/mm]
Du hast gesagt, ich kann das c= min{a,b,d} wählen. Angenommen, dass Minimum davon wäre a. Muss dann a nicht [mm] \le [/mm] 1 sein, weil links von der Ungleichung vor [mm] n^{3} [/mm] eine 1 steht?
Oder kann ich auch sagen, dass das min{a,b,d}= a ist und c so wählen:
c = [mm] \bruch{a}{bd} [/mm] für b,d [mm] \not= [/mm] 0? Der Bruch ist dann auf jeden Fall kleiner 1 und die Ungleichung lautet:
[mm] n^{3} [/mm] + a [mm] n^{2} [/mm] + b n + d [mm] \ge \bruch{a}{bd} n^{3}
[/mm]
Dies stimmt schon für alle n [mm] \ge [/mm] 0.
Geht das auch so?
Auch hier hab ich das Problem, wie ich das [mm] n_{0} [/mm] auch in Abh. von a,b,d wählen soll.
Ich hoffe, du hilfst mir weiter.
Danke nochmal :)
Schönen Abend,
wetterfrosch
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 08:20 Di 23.05.2006 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
