算法分析(大O和大欧米茄)

Question

我在考试中做错了这道题:命名一个既不是 O(n) 也不是 Omega(n) 的函数。

在尝试通过 youtube 自学这些东西之后，我认为这可能是一个正确的答案:

(n³ (1 + sin n)) is neither O(n) nor Omega(n).

这会准确吗？

Answer 1

Name a function that is neither O(n) nor 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, ∞) 上任意接近于零。

I'm thinking this may be a correct answer: (n^3 (1 + sin n)) is neither O(n) nor 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 的任何正常数倍数限制，也不受其限制。