O-Notation

Neue Frage »

Ladi Auf diesen Beitrag antworten »
O-Notation
Meine Frage:
Es sei f1 element O(g)und es sei f2 element O(g). Beweise/Wiederlege f1+f2 ist element O(g)



Meine Ideen:
Laut Def. ist f(n) < c*g(n)
Also ich würde dann so beginnen: f1(n)+ f2(n) < c*g1(n) + c*g2(n)
f1(n)+f2(n) < c ( g1(n)+g2(n))

Ist zumindest der Ansatz richtig ??
Danke für die Hilfe
Hubert1965 Auf diesen Beitrag antworten »

Der Ansatz ist prinzipiell richtig und auch zielführend, aber leider nicht ganz korrekt ausgeführt.

1)
Statt

solltest du besser

schreiben.

2)
Das ist falsch:

richtig wäre:

Die beiden Konstanten sind ja nicht notwendigerweise identisch!
gitterrost4 Auf diesen Beitrag antworten »

Zitat:
Original von Hubert1965
richtig wäre:



Nicht ganz. Es gibt nur ein und nicht etwa und
Ladi Auf diesen Beitrag antworten »

Gut, dann ist f1(n) +f2(n) kleiner gleich c1 * g(n) +c2* g(n)
wie verfahre ich weiter ?
Meine weitere Idee wäre: lim f1(n) +f2(n) / g(n) (c1+c2) sollte 0 oder c sein....und durch das könnte ich zeigen, dass es stimmt.....bin mir nicht sicher und freue mich über jegliche Hilfe !

anderer Vorschlag meiner Seite wär: die Gleichung f1(n) +f2(n) kleiner gleich c1 * g(n) +c2* g(n) so umzuformen dass f1(n)+f2(n) / c1+c2 kleiner gleich g(n) ist....hab ich das dann gezeigt damit ?


Danke für die obige Beantwortung !
Math1986 Auf diesen Beitrag antworten »

Jetzt bist du fertig, es gilt doch
Ladi Auf diesen Beitrag antworten »

Danke das hat mir sehr geholfen ;-)
 
 
Ladi Auf diesen Beitrag antworten »

andere fast gleiche Fragestellung: Wenn f1 element O(g1) und f2 element O(g2) ist und f2(n) >0
ist giltet dann f1/f2 element O(g1/g2) ??
Mein Ansatz wäre wieder ähnlich: nur komme ich dann auf f1(n) * c2 / f2(n)*c1 kleiner gleich g1(n)/g2(n)...........habe ich damit das beispiel wiederlegt ??? Oder habe ich es bewiesen ?? Kann mir jemand ein Beispiel geben ?
Danke für die Hilfe !!!
Math1986 Auf diesen Beitrag antworten »

Nutze zukünftig den Formeleditor!
Und eröffne für neue Fragen bitte auch einen neuen Thread

Du hast doch



Nun kannst du abschätzen

Wi liegt das Problem?

EDIT1: Ich sehe das Problem, so einfach wie ich geschrieben habe gehts nicht, da die eine grössere Zahl im Nenner steht
Ladi Auf diesen Beitrag antworten »

Danke für den Link des Formeleditors, hab nicht gewusst dass es so etwas gibt !
Das Problem ist nicht nur das die größere Zahl im Nenner steht sondern auch das die zwei Funktionen in einer anderen O(g) liegen.....daher hatte ich auch den Begriff "g1" "g2" verwendet...

Danke vielmals für deine Hilfe !
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »