算法分析(Big O和Big Omega)

Question

我在考试中得到了这个问题:命名一个既不是O(n)也不是Omega(n)的函数.

在尝试通过youtube自己学习这些东西后,我想这可能是一个正确的答案:

(n ³(1 + sin n))既不是O(n)也不是Omega(n).

那会准确吗？

Answer 1

命名既不是O(n)也不是Omega(n)的函数

说f ? O(g)是指商

f(x)/g(x)

所有足够大的都是从上面限制的x.

f ? ?(g) 另一方面,意思是商

f(x)/g(x)

所有足够大的地方都远离零x.

因此,要找到一个函数,也不是O(n)也不?(n)意味着找到一个功能f,使得商

f(x)/x

变得任意大,并且在每个间隔上任意接近于零[y, ?).

我认为这可能是一个正确的答案:(n^3 (1 + sin n))既不是O(n)也不是Omega(n).

让我们把它插入我们的商:

(n^3*(1 + sin n))/n = n^2*(1 + sin n)

在n^2长到无限大,且系数1 + sin n大于1的大致有三种每六个n.因此,每个区间[y, ?)的商都变得任意大.给予任意K > 0,让N_0 = y + K + 1和N_1最小的N_0 + i, i = 0, 1, ..., 4这样的sin (N_0+i) > 0.然后f(N_1)/N_1 > (y + K + 1)² > K² + K > K.

对于这?(n)部分来说,虽然我认为它很满意,但它并不容易证明.

但是,我们可以对函数进行一些修改,保留将增长函数与振荡函数相乘的思想,使证明变得简单.

而不是sin n让我们选择cos (?*n),并且,为了抵消零,为它添加一个快速递减函数.

f'(n) = n^3*(1 + cos (?*n) + 1/n^4)

现在,

         / n^3*(2 + 1/n^4), if n is even
f'(n) = <
         \  1/n           , if n is odd

很明显,f'既不是从上面,也不是从下面以任何正的常数倍n.