我在考试中答错了这个问题：命名一个既不是 O(n) 也不是 Omega(n) 的函数。
在尝试通过 youtube 自己学习这些东西之后，我认为这可能是一个正确的答案：
(n 3 (1 + sin n)) 既不是 O(n) 也不是 Omega(n)。
那会准确吗？
问问题
2355 次
2 回答
5
命名一个既不是 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。
于 2012-12-14T04:14:56.497 回答
0
我会考虑类似于二进制搜索的东西。这是 O(log N) 和 Ω(log N)。由于 Omega 被定义为下限，因此不允许超过函数本身——所以 O(log N) 绝对不是 Ω(N)。
我认为对已删除答案的一些评论应该得到一些……澄清——甚至可能是彻底的更正。引用 CLRS 的话，“Ω 表示法给出了函数在常数因子内的下限。”
由于 N 2与 N 的差异超过一个常数因子，因此 N 2不是Ω(N)。
于 2012-12-14T03:31:40.947 回答