渐近符号
这是 MIT 开放课程算法简介作业中关于渐近符号的问题：
对于以下每个陈述，确定对于渐近非负函数，它是始终为真、从不为真还是有时为真f< /em> 和 g。如果它始终为真或从不为真，请解释原因。如果它有时为真，请给出一个正确的例子和一个错误的例子。
f(n) ≠ O(g(n)) and g(n) ≠ O(f(n)) (both are Big-O notes)
我认为这从来都不是真的。这是我的证明：
f(n) ≠ O(g(n))
=> f(n) = w(g(n)) (little-omega note)
=> g(n) = o(f(n)) (little-o note)
=> g(n) = O(f(n)) (big-O note)
结果与g(n) ≠ O(f(n))（Big-O note）矛盾。同样，
g(n) ≠ O(f(n))
=> g(n) = w(f(n)) (little-omega note)
=> f(n) = o(g(n)) (little-o note)
=> f(n) = O(g(n)) (big-O note)
这与 f(n) ≠ O(g(n)) （大 O 注释） 相矛盾。
解决方案说它有时是正确的：
For f(n) = 1 and g(n) = ||n*sin(n)|| it is true,
while for any f(n) = O(g(n)), e.g. f(n) = g(n) = 1, it is not true.
我在证明中哪里做错了？另外，我无法理解该解决方案。 ||n*sin(n)|| 对我来说看起来像向量范数。
This is a problem on Asymptotic Notation from the assignment of MIT OpenCourse Introduction to Algorithm:
For each of the following statements, decide whether it is always true, never true, or sometimes true for asymptotically nonnegative functions f and g. If it is always true or never true, explain why. If it is sometimes true, give one example for which it is true, and one for which it is false.
f(n) ≠ O(g(n)) and g(n) ≠ O(f(n)) (both are Big-O notes)
I think it is never true. Here's my proof:
f(n) ≠ O(g(n))
=> f(n) = w(g(n)) (little-omega note)
=> g(n) = o(f(n)) (little-o note)
=> g(n) = O(f(n)) (big-O note)
the result contradicts to g(n) ≠ O(f(n)) (Big-O note). Likewise,
g(n) ≠ O(f(n))
=> g(n) = w(f(n)) (little-omega note)
=> f(n) = o(g(n)) (little-o note)
=> f(n) = O(g(n)) (big-O note)
which contradicts to f(n) ≠ O(g(n)) (Big-O note).
The solution says it is sometimes true:
For f(n) = 1 and g(n) = ||n*sin(n)|| it is true,
while for any f(n) = O(g(n)), e.g. f(n) = g(n) = 1, it is not true.
Where have I done wrong in my proof? Also, I cannot understand the solution. ||n*sin(n)|| looks like vector norm to me.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
我认为 n*sin(n) 只是表明它是一个不断变大的函数。对于 n 的后续值，即使对于用于定义 Big O & 的常数乘数的所有选择，也小于
f(n) = 1因此f(n) ≠ O(g(n)) 且 g(n) ≠ O(f(n))一个天真的选择的函数，如
g(n) = 2*sin( n)在这里效果不佳。人们可能会认为这也会在f(n) = 1周围不断交替，但是g(n) = O(f(n)) : M*f(n) > g(n) for M = 3等I think
n*sin(n)just shows that it is a function which keeps getting larger & smaller thanf(n) = 1for subsequent values of n even for all choices of a constant multiplier used for defining Big O & thusf(n) ≠ O(g(n)) and g(n) ≠ O(f(n))A Naively chosen function like
g(n) = 2*sin(n)won't do good here. One might think that this would also keep alternating aroundf(n) = 1, butg(n) = O(f(n)) : M*f(n) > g(n) for M = 3etc第一个是不正确的：从这个
f(n) ≠ O(g(n))来看，它不遵循以下规则：f(n) = w(g(n))代码>.这两个函数可能会在某个点相交，然后发生重叠，另一个函数会变得更大（如果我使用简单的词）。他们选择的函数就是这种情况：对于 n <= 1，第一个 f(n) > g(n) 且存在 ns ，其中 g(n) > f(n)（例如 pi / 2）。
The first is not true : from this
f(n) ≠ O(g(n))it does not follow this:f(n) = w(g(n)). The two functions might intersect at some point and then slap places, the other becoming bigger (if I use simple words).The function they chose is just this case: for n <= 1 the first f(n) > g(n) and there exist ns for which g(n) > f(n) (e.g pi / 2).