Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
-- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
--- O-Notation quadratische Komplexität (http://www.informatikerboard.de/board/thread.php?threadid=2968)
Geschrieben von Zugspitze am 22.04.2016 um 13:11:
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
Geschrieben von eulerscheZahl am 22.04.2016 um 19:00:
Die Definition für die O Notation wäre ein guter Ansatz. Schreibe die mal auf.
Geschrieben von Zugspritze am 22.04.2016 um 19:18:
| 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
Geschrieben von eulerscheZahl am 22.04.2016 um 19:25:
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?
Geschrieben von Zugspitze am 22.04.2016 um 19:27:
C1= a+b+c
C2=-a-b-c
Und n=1 oder ??
Geschrieben von Zugspitze am 22.04.2016 um 19:28:
Was ist dieses const ??
Geschrieben von eulerscheZahl am 22.04.2016 um 19:29:
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.
Geschrieben von Zugspritze am 22.04.2016 um 19:35:
Ahso ok
C1 und c2 sind die zugehörigen konstanten die man bestimmen soll
Geschrieben von eulerscheZahl am 22.04.2016 um 19:37:
| Zitat: |
| Deshalb hatte ich dich gebeten, die Definition der O Notation aufzuschreiben |
ein viertes Mal werde ich dich nicht darum bitten.
Geschrieben von Zugspritze am 22.04.2016 um 19:42:
Also ich hab nur diese Definition, ich glaub nicht das es weiter hilft
T(n)=O(f(n))
T(n)=< c *f(n)
Geschrieben von eulerscheZahl am 22.04.2016 um 19:44:
Und hier hast du eine Konstante c.
Die hatte ich const genannt, damit du sie nicht mit dem c aus dem Polynom verwechselst.
Geschrieben von Zugspritze am 22.04.2016 um 19:47:
Ahso ok dann ist c1 = |a|+|b|+|c| Oder ?
Und wenn ja was ist denn c 2
Geschrieben von eulerscheZahl am 22.04.2016 um 19:49:
Du solltest mir sagen, welche Bedeutung c2 hat.
Geschrieben von Zugspritze am 22.04.2016 um 19:55:
Da bin ich mir selber nicht sicher, es stand aufjedenfall in der Aufgabe
Geschrieben von eulerscheZahl am 22.04.2016 um 19:57:
Ich habe keine Lust auf Rätselraten. Solange du mir nicht sagst, was du gegeben hast, bin ich raus.
Forensoftware: Burning Board, entwickelt von WoltLab GmbH