Сравнение сложности времени выполнения для n ^ a * log (n) ^ b и n ^ c * log (n) ^ d

Question

Я работаю над проблемой, где мне дают f (n) = n ^ 2 * (log (n)) ^ - 1, и g (n) = n (log (n)) ^ 2, ипопросили определить, есть ли f = O (g), f = омега (g) или оба (f = тета (g)).

Эта проблема может быть обобщена на (n ^ a) * log (n) ^ b и (n ^ c) * log (n) ^ d

Я понимаю, что любой многочлен доминирует над любым логарифмом, например, n доминирует над log (n) и, кроме того, n ^ 2 доминирует над nlog (n), однакоЯ не уверен, как адаптировать это к более сложным проблемам, например:

• f = (n ^ 2) * log (n) ^ - 1000, g = (n) * log (n) ^ 1000

или еще лучше:

• f = n ^ .01, g = log (n) ^ 10

Полиномиальный член всегда определяет, доминирует ли f над g, или наоборот?Если так, то почему?и если нет, то как можно решить проблему?

Спасибо!

Answer 1

Ответ: n^a * log(n)^b доминирует n^c * log(n)^d, если a > c.Другими словами, вам нужно только взглянуть на полиномиальную часть.(Если, конечно, a=c, в этом случае вы смотрите на часть полилога.)

Это потому, что полилогарифмические функции всегда асимптотически меньше полиномиальных функций.Точнее, если p(n) = a*(log n)^b (p является полилогарифмическим в n), то p(n) = o(n^epsilon) для любого epsilon > 0 (см. на этой странице Википедии для формального утверждения и этот ответ для доказательства).

Итак, у нас есть n^a * log(n)^b = o(n^(a + epsilon)) для любого epsilon > 0.Из этого должно быть легко прийти к ответу выше.