确定Big-Oh / Big-Theta或Big-Omega

Question

给定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

那么，人们如何证明它属于哪一个呢？或者它既不属于它们也不属于它们，因为它根本没有边界...？

Answer 1

考虑序列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)不是欧米茄(g(N))，那么f(n)就没有资格成为θ(g(N))。

注: f(n) = O(A(n))和f(n) = O(B(n))。f(n) =θ( h(n) )，其中h(N)是任何像f(n)一样振荡的函数，它的增长速度至少一样快，并且有一个恒定的下界。