Как найти соотношение этих двух функций, когда мы рассматриваем сложность времени?

Question

Например, как и вопрос ниже, могу ли я решить этот вопрос, просто выполнив тест сравнения пределов?

Пусть f (n) = n · (4 ^ n) и g (n) = 2 ^ (3n)

, какое соотношение лучше всего применимо:

f ( n) ≤ O (g (n)), f (n) ≥ Ω (g (n)) или f (n) = Θ (g (n))?

Answer 1

Да, предельные тесты - фактически определение этой нотации. Для приведенного примера | f (n) | / g (n) равно n * 2 ^-n , поэтому f (n) = O (g (n)) верно, но f (n) = Ω (g (n)), и, следовательно, f (n) = Θ (g (n)) неверно.

Answer 2

Как мы знаем 2^(3n) = 8^n:

lim_{n \to \infty} (f(n)/g(n) = n * 4^n / 8^n = n/2^n)

Поскольку рост 2^n быстрее, чем n, вышеуказанный предел равен нулю. Следовательно, f(n) = o(g(n)) (мало-ой).

Answer 3

f(n) = ω(g(n)) IF:
(lim n-> Infinity [f (n) / g (n)] = бесконечность)
И f(n) = o(g(n)) IF:
(lim n-> Infinity [ f (n) / g (n)] = 0)
Надеюсь, это поможет.