大 O 表示法 1/O(n) = Omega(n)
我收到了证明 1/O(n) = Ω(n) 的作业
，但是，这意味着 O(n) => 的 元素这显然是错误的。n 元素; Ω(n) 的 1/n
所以我的问题是：语句 1/O(n) = Ω(n) 正确吗？
编辑：我向写问题的助理发送了一封电子邮件。并使用了f(n) = 1的例子。 他随后表示，这种说法确实不正确。
I have received the assignment to prove 1/O(n) = Ω(n)
However, this would mean that n element of O(n) => 1/n element of Ω(n) which is clearly wrong.
So my question is: Is the statement 1/O(n) = Ω(n) correct?
EDIT: I send an Email to the assistant who wrote the questions. And used the example of f(n) = 1.
He then said, that the statement is indeed incorrect.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
符号 1/O(n) = Ω(n) 有点模糊。本身确实没有O(n)，只有f(n) ~ O(n)，这是关于函数值的声明 f（有一个常数C，因此对于每个n，f(n) < Cn）。
如果我理解正确的话，要证明的陈述是“如果函数 f(n) 是 O(n) 比 1/f(n)< /em> 为 Ω(n)”，形式为：
f(n) ~ O(n) => 1/f(n) ~ Ω(n)
编辑：除了我认为我理解不正确，因为f(n) = 1 ~ O(n) ，但1/f(n) = f(n) = 1显然不是Ω(n)。赋值不是f(n) ~ O(n) => 1/f(n) ~ Ω(1/n) 代替？
编辑：不同的人倾向于使用不同的运算符。最常见的是f(n) = O(n)，但这很令人困惑，因为右侧不是函数，所以它不能是正常的相等。我们在学校通常使用 f(n) ~ O(n)，这不太容易混淆，但仍然与该运算符在一般等价关系中的常见用法不一致。最一致的运算符将是 f(n) ∈ O(n)，因为右侧可以合理地视为函数集。
The notation 1/O(n) = Ω(n) is a bit vague. There is really no O(n) on it's own, there is only f(n) ~ O(n), which is a statement about values of function f (there is a constant C so that f(n) < Cn for each n).
And the statement to prove, if I understand it correctly, is "if function f(n) is O(n) than 1/f(n) is Ω(n)", formally:
f(n) ~ O(n) => 1/f(n) ~ Ω(n)
Edit: Except I don't think I understand it correctly, because f(n) = 1 ~ O(n), but 1/f(n) = f(n) = 1 is clearly isn't Ω(n). Weren't the assignment f(n) ~ O(n) => 1/f(n) ~ Ω(1/n) instead?
Edit: Different people tend to use different operators. Most common is f(n) = O(n), but that is confusing because the right hand side is not a function, so it can't be normal equality. We usually used f(n) ~ O(n) in school, which is less confusing, but still inconsistent with common use of that operator for general equivalence relations. Most consistent operator would be f(n) ∈ O(n), because the right hand side can reasonably be treated as set of functions.
对于某些多项式函数 f(x)、某些多项式函数 g(x) 和 O(f(x))，O(n) 或多或少意味着以下含义：
就幅度而言，我们有 |f(x)| <= M|g(x)|，对于某个 M。基本上，f 的边界是常数乘以 g。
Ω(n) 意味着，对于某些多项式 h(x)、某些多项式 k(x) 和 Ω(h(x))：
就幅度而言，|h(x)| >= M|k(x)|，对于某个 M。基本上，h 的边界是常数乘以 k。
因此，对于 (O(f(x)))^-1, 1/|f(x)| <= 1/(M|g(x)|)。
稍微重新排列一下就可以得到 M|g(x)| <= |f(x)| - 即 f(x) 的边界是常数乘以 g，这与我们上面对 Ω(n) 的定义完全相同。
作为正式证明有点粗糙，但它应该可以帮助您入门。
O(n) more or less implies the following, for some polynomial function f(x), some polynomial function g(x) and O(f(x)):
In terms of magnitude, we have |f(x)| <= M|g(x)|, for some M. Basically, f is bounded above by a constant times g.
Ω(n) implies that, for some polynomial h(x), some polynomial k(x) and Ω(h(x)):
In terms of magnitude, |h(x)| >= M|k(x)|, for some M. Basically, h is bounded below by a constant times k.
So, for (O(f(x)))^-1, 1/|f(x)| <= 1/(M|g(x)|).
A bit of re-arranging gives M|g(x)| <= |f(x)| - i.e. f(x) is bounded below by a constant times g, which is exactly the same as our definition for Ω(n) above.
It's a tad scratchy to be a formal proof, but it should get you started.