 O-Notation quadratische Komplexität |
Zugspitze
unregistriert
 |
|
| 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 13:11 |
|
|
Zugspritze
unregistriert
|
|
| Zitat: |
Original von eulerscheZahl
Die Definition für die O Notation wäre ein guter Ansatz. Schreibe die mal auf. |
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:18 |
|
|
|
|
Also, wir haben:
![[latex]a\cdot n^2+b\cdot n+c \underbrace{\leq}_{n\geq 1} (a+|b|+|c|)\cdot n^2[/latex]](http://www.matheboard.de/latex2png/latex2png.php?a\cdot n^2+b\cdot n+c \underbrace{\leq}_{n\geq 1} (a+|b|+|c|)\cdot n^2) .
Nach Definition der O Notation muss gelten:
\cdot n^2 \leq const \cdot n^2[/latex]](http://www.matheboard.de/latex2png/latex2png.php?(a+|b|+|c|)\cdot n^2 \leq const \cdot n^2)
Wie muss die Konstante gewählt werden und ab welchem n gilt das, damit die Ungleichung erfüllt ist?
__________________
Syntax Highlighting fürs Board (Link)
|
|
|
22.04.2016 19:25 |
|
|
Zugspitze
unregistriert
|
|
C1= a+b+c
C2=-a-b-c
Und n=1 oder ??
|
|
|
22.04.2016 19:27 |
|
|
Zugspitze
unregistriert
|
|
|
|
22.04.2016 19:28 |
|
|
|
|
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.
__________________
Syntax Highlighting fürs Board (Link)
|
|
|
22.04.2016 19:29 |
|
|
Zugspritze
unregistriert
|
|
Ahso ok
C1 und c2 sind die zugehörigen konstanten die man bestimmen soll
|
|
|
22.04.2016 19:35 |
|
|
|
|
| Zitat: |
| Deshalb hatte ich dich gebeten, die Definition der O Notation aufzuschreiben |
ein viertes Mal werde ich dich nicht darum bitten.
__________________
Syntax Highlighting fürs Board (Link)
|
|
|
22.04.2016 19:37 |
|
|
Zugspritze
unregistriert
|
|
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:42 |
|
|
Zugspritze
unregistriert
|
|
Ahso ok dann ist c1 = |a|+|b|+|c| Oder ?
Und wenn ja was ist denn c 2
|
|
|
22.04.2016 19:47 |
|
|
Zugspritze
unregistriert
|
|
Da bin ich mir selber nicht sicher, es stand aufjedenfall in der Aufgabe
|
|
|
22.04.2016 19:55 |
|
|
|
