| Info-Neuling |
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? |
