Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Informatik O-Notation formaler Beweis

Informatik O-Notation formaler Beweis

Universität / Fachhochschule

Funktionen

Tags: Funktion, informatik, O-Notation

Masemo1234 aktiv_icon

14:15 Uhr, 12.10.2017

Hallo liebes Matheforum,
das ist vielleicht nicht direkt euer gebiet aber das Problem was ich habe ist schon ziemlich Mathematisch. Ich belege dieses Semester Algorithmen und Berechnungskomplexität. In der vorlesung haben wir die O-Notation besprochen und ich verstehe sie auch. Auf dem Übungsblatt sollen wir jetzt Aussagen zur O-Notation Beweisen und ich hänge seit Stunden an dem formalen Beweis. Anscheinend waren die Semesterferiern zu lang. Ich denke wenn ich verstanden habe wie eine Aussage zu beweisen ist werde ich auch die anderen schaffen. Die aufgabe ist wier folgt:

Es seien

p 1 (n) = a 1 \cdot n^{d 1}

und

p 2 (n) = a 2 \cdot n^{d 2}

Polynome vom Grad

d 1

bzw

d 2,

wobei die Koeffizienten

a 1

und

a 2

positiv sind. Zeigen Sie, dass dann die folgenden Aussagen gelten:

(a)

p 1 = Θ (p 2) \Leftrightarrow d 1 = d 2

(Ich bin davon ausgegangen, dass es

p 1 \in Θ (p 2)

heißen soll)

Die äquivalenz der Aussagen scheint mir logisch aber beim einsetzten der Definition von

Θ

scheitere ich an den Koeffizienten.
Etwa so:

(a 1 \cdot n^{d 1} \leq c \cdot a 2 \cdot n^{d 2}) \land (a 2 \cdot n^{d 2} \leq c \cdot a 1 \cdot n^{d 1}) \Leftrightarrow d 1 = d 2

Ohne die Koeffizienten wäre die aussage ja logisch, aber ich stehe auf dem Schlauch.
Oder ist vielleicht mein ganzer Ansatz falsch.
Vielen Dank in Voraus für die Hilfe.
Marius

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

Hierzu passend bei OnlineMathe:
Funktion (Mathematischer Grundbegriff)

Online-Übungen (Übungsaufgaben) bei unterricht.de:

Einführung Funktionen