Komplexitätsanalyse nach der Multiplikation von zwei Funktionen

Question

Da F (n) = θ (n)

H (n) = O (n)

G (n) = Ω (n)

Was ist dann die Reihenfolge von F (n) + [G (n). H (n)]?

edit: F (n) = θ (n) nicht Q (n)

Answer 1

Es gibt nicht genügend Informationen, um zu sagen nichts über die Funktion P(n) = G(n)*H(n). Alles, was wir wissen ist, dass G wächst mindestens linear; es könnte quadratisch, kubisch, sogar exponentiell wachsen. Ebenso wissen wir nur, dass Hhöchstens linear wächst; es konnte nur logarithmisch wachsen oder konstant sein oder sogar absteigend sein. Als Ergebnis könnte P(n) selbst ohne Bindung abnehmen oder zunehmen, was bedeutet, dass die Summe F(n) + P(n) auch ohne Bindung abnehmen oder zunehmen könnte.

Angenommen, wir könnten annehmen, dass H(n) = Ω(1) (d. H. Es ist zumindest nicht abnehmend). Jetzt können wir sagen folgendes über P(n):

P(n) = H(n) * G(n) 
    >= C1 * G(n) 
    = Ω(G(n)) = Ω(n) 

P(n) <= C1*n * G(n) 
     = O(n*G(n)) 

So F(n) + P(n) = Ω(n) und F(n) + P(n) = O(n*G(n)), aber nichts mehr gesagt werden kann; Beide Grenzen sind so eng, wie wir sie ohne weitere Informationen über H oder G machen können.