Info-Neuling
Grünschnabel
Dabei seit: 02.05.2016
Beiträge: 1
 |
|
| Zusammenhänge asymptotischer Beziehungen |
     |
Meine Frage:
Hallo Informatik-Freunde,
ich stehe gerade vor folgendem Problem.
Es seien f, f1, f2, g, g1, g2 : N ? R?0 Funktionen, die Laufzeiten bestimmen.
Zeigen oder widerlegen Sie die folgenden Aussagen:
(a) f1 = omega(g1) logisches und f2 = omega(g2) -> f1 + f2 = omega(g1 + g2).
(b) f1 = Theta(g1) logisches und f2 = Theta(g2) -> f1 · f2 = Theta(g1 · g2).
(c) f = O(g) -> 2^f = O(2^g)
(d) f = o(g) -> f = O(g).
(e) f = O(g) -> f = o(g).
(f) f(n) = g(n/2) -> f = 
g).
Könnte da mal jemand ein Auge drauf werfen? Mein Ansatz s.U.
Danke
Meine Ideen:
Ich habe mir dazu schon ein paar Gedanken gemacht, komme aber gerade nicht wirklich weiter.
Bei a) würde ich sagen, es ist korrekt.
Bei b) bin ich mir nicht ganz sicher.
Bei c) sollte doch stimmen.
Bei d) : kann man von "f wächst langsamer als g" auf "f wächst höchstens so schnell wie g" schließen. Man kann doch eigentlich nicht von der kleineren Menge auf die größere schließen, oder?
Bei e) das gleiche spiel nur andersherum?
Bei f) f wächst mindestens so schnell wie g, stimmt oder?
Dieser Beitrag wurde 3 mal editiert, zum letzten Mal von Info-Neuling: 02.05.2016 11:09.
|
|
