O-Notation quadratische Komplexität |
22.04.2016, 13:11 | Auf diesen Beitrag antworten » | ||
Zugspitze | O-Notation quadratische Komplexität Meine Frage: Wie kann man die quadratische Komplexität beweisen? Zeige für a,b,c Element aus R, a>0 gibt an^2 +bn+c = O(n^2) Und dann soll ich die passenden Konstanten c1,c2,n0 angeben Meine Ideen: Ich hoffe jemand kann mir helfen oder hat einen Ansatz für mich |
||
|
|||
22.04.2016, 19:00 | Auf diesen Beitrag antworten » | ||
eulerscheZahl | Die Definition für die O Notation wäre ein guter Ansatz. Schreibe die mal auf. |
||
22.04.2016, 19:18 | Auf diesen Beitrag antworten » | ||
Zugspritze |
Also das hab ich aufgeschrieben an^2+bn+c =< n^2 an^2+bn+c =< |a| n^2+ |b| n+ |c| =< |a|n^2+ |b|n^2 +|c|n^2 Weiter weiß ich nicht und ich weiß auch nicht wie ich die konstanten bestimmen kann |
||
22.04.2016, 19:25 | Auf diesen Beitrag antworten » | ||
eulerscheZahl | Also, wir haben: . Nach Definition der O Notation muss gelten: Wie muss die Konstante gewählt werden und ab welchem n gilt das, damit die Ungleichung erfüllt ist? |
||
Anzeige | |||
|
|||
22.04.2016, 19:27 | Auf diesen Beitrag antworten » | ||
Zugspitze | C1= a+b+c C2=-a-b-c Und n=1 oder ?? |
||
22.04.2016, 19:28 | Auf diesen Beitrag antworten » | ||
Zugspitze | Was ist dieses const ?? |
||
22.04.2016, 19:29 | Auf diesen Beitrag antworten » | ||
eulerscheZahl | Deshalb hatte ich dich gebeten, die Definition der O Notation aufzuschreiben, die wird je nach Quelle leicht anders definiert. Ich weiß nicht, was du mit C1 und C2 meinst. |
||
22.04.2016, 19:35 | Auf diesen Beitrag antworten » | ||
Zugspritze | Ahso ok C1 und c2 sind die zugehörigen konstanten die man bestimmen soll |
||
22.04.2016, 19:37 | Auf diesen Beitrag antworten » | ||
eulerscheZahl |
ein viertes Mal werde ich dich nicht darum bitten. |
||
22.04.2016, 19:42 | Auf diesen Beitrag antworten » | ||
Zugspritze | Also ich hab nur diese Definition, ich glaub nicht das es weiter hilft T(n)=O(f(n)) T(n)=< c *f(n) |
||
22.04.2016, 19:44 | Auf diesen Beitrag antworten » | ||
eulerscheZahl | Und hier hast du eine Konstante c. Die hatte ich const genannt, damit du sie nicht mit dem c aus dem Polynom verwechselst. |
||
22.04.2016, 19:47 | Auf diesen Beitrag antworten » | ||
Zugspritze | Ahso ok dann ist c1 = |a|+|b|+|c| Oder ? Und wenn ja was ist denn c 2 |
||
22.04.2016, 19:49 | Auf diesen Beitrag antworten » | ||
eulerscheZahl | Du solltest mir sagen, welche Bedeutung c2 hat. |
||
22.04.2016, 19:55 | Auf diesen Beitrag antworten » | ||
Zugspritze | Da bin ich mir selber nicht sicher, es stand aufjedenfall in der Aufgabe |
||
22.04.2016, 19:57 | Auf diesen Beitrag antworten » | ||
eulerscheZahl | Ich habe keine Lust auf Rätselraten. Solange du mir nicht sagst, was du gegeben hast, bin ich raus. |
|