Анализ сложности после умножения двух функций

Учитывая F (n) = θ (n)

H (n) = O (n)

G (n) = Ω (n)

то каков будет порядок F (n) + [G (n). H (n)]?

edit: F (n) = θ (n) не Q (n)

1 ответ

Недостаточно информации, чтобы сказать что-нибудь о функции P(n) = G(n)*H(n). Все, что мы знаем, это то, что G растет, по крайней мере, линейно; он может расти квадратично, кубически, даже экспоненциально. Аналогично, мы знаем только, что H растет не более линейно; он может только логарифмически возрастать или быть постоянным или даже уменьшаться. В результате сам P(n) мог уменьшаться или увеличиваться без ограничений, что означает, что сумма F(n) + P(n) также может уменьшаться или увеличиваться без ограничений.

Предположим, однако, что мы можем предположить, что H(n) = Ω(1) (т.е., по крайней мере, не уменьшается). Теперь мы можем сказать следующее о P(n):

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

Таким образом, F(n) + P(n) = Ω(n) и F(n) + P(n) = O(n*G(n)), но ничего более нельзя сказать; обе границы настолько плотные, что мы можем сделать их без дополнительной информации о H или G.

licensed under cc by-sa 3.0 with attribution.