Блог

Учитывая f (n) = n ^ [(1 sin (n * pi / 2)) / 2] и g (n) = n ^ 0,5, как мне доказать, что f (n) = O (g (n)) / f (n) = Omega (g (n)) / f (n) = Theta (g (n)).

Я выяснил, что f (n), похоже, не имеет границы, поскольку функция становится больше и меньше по мере увеличения n…. (я построил график здесь)https://www.desmos.com/calculator/xtrh124rjb

Итак, как можно обосновать, к какому из них оно принадлежит? Или это не принадлежит ни одному из них, поскольку у него вообще нет границы ….?

Рассмотрим последовательность 1, 5, 9, …, 4k 1, … Для этих значений n, (1 sin (n * pi / 2)) / 2 = 1. Следовательно, для этих значений n ваша функция идентична функции A (n) = n ^ 1 = n. Обратите внимание, что A (n) = n НЕ является O (g (n)) = O (n ^ 0.5); n растет асимптотически быстрее, чем n ^ 0.5.

Рассмотрим последовательность 3, 7, 11, …, 4k 3, … Для этих значений n, (1 sin (n * pi / 2)) / 2 = 0. Следовательно, для этих значений n ваша функция идентична функции B (N) = n ^ 0 = 1. Обратите внимание, что B (n) = 1 НЕ является Omega (g (n)) = Omega(n ^ 0.5); n ^ 0.5 растет асимптотически быстрее, чем константа 1 (которая вообще не растет).

Либо f (n) не является O (g (n)) Или f (n), не являющееся Omega(g (n)), уже лишило бы f (n) статуса Theta (g (n)).

Примечание: f (n) = O (A (n)) и f (n) = O (B (n)). f (n) = Theta (h (n)) где h (n) — любая функция, которая колеблется подобно f (n) и которая растет по крайней мере с такой же скоростью и которая имеет постоянную нижнюю границу.