algorithm - 算法分析（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 n1 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。

Answer 2

我会考虑类似于二进制搜索的东西。这是 O(log N) 和 Ω(log N)。由于 Omega 被定义为下限，因此不允许超过函数本身——所以 O(log N) 绝对不是 Ω(N)。

我认为对已删除答案的一些评论应该得到一些……澄清——甚至可能是彻底的更正。引用 CLRS 的话，“Ω 表示法给出了函数在常数因子内的下限。”

由于 N ²与 N 的差异超过一个常数因子，因此 N ²不是Ω(N)。