渐近记法

这是麻省理工学院OpenCourse 介绍的分配算法上渐近记法一个问题：
对于每一个下面的语句，决定是否总是如此，从来没有真正，或有时真正渐近非负函数˚F和克。如果是总是如此或从未真正，解释原因。如果是有时真，举个例子，这就是它真正的，一个是它是假的。渐近记法

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)) (Big-O note)矛盾。

解决方案说，这是有时真：

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)||看起来像向量规范给我。

来源

2012-02-18 manuzhang

假设||ñ罪（N）||应该阅读| n sin（n）|并参考实数的绝对值（当然，这是R^1上的向量范数），反例是有意义的。本来可以选择n *（1 +（ - 1）^ n）= 0，0，2，0，4，0，6 ......代替。 – tiwo 2012-07-21 20:11:38

一个教学旁注：也许你想要f = O（g）是一组函数的偏序，因为它对于实数f，g感觉非常类似f≤g。 – tiwo 2012-07-21 20:19:14

首先是不正确的：从这个f(n) ≠ O(g(n))它不遵循这样：f(n) = w(g(n))。这两个函数可能会在某一点相交，然后拍一个地方，另一个变得更大（如果我使用简单的话）。他们选择的函数就是这种情况：对于n < = 1，第一个f（n）> g（n）并且存在其中g（n）> f（n）（例如pi/2）的ns，。

来源

2012-02-18 12:24:28

我觉得n*sin(n)只是表明它是不断变大&小于f(n) = 1对于n的后续值甚至用来定义大O &从而f(n) ≠ O(g(n)) and g(n) ≠ O(f(n))

A中的系数器的所有选项的功能天真选择的功能，如g(n) = 2*sin(n)在这里不会有好处。有人可能会认为，这也将保持交替各地f(n) = 1，但g(n) = O(f(n)) : M*f(n) > g(n) for M = 3等

来源

2012-02-18 12:53:05 shiraz

确实，像'n * sin（n）'这样的功能就这么漂亮 – manuzhang 2012-02-18 13:39:06

回答

相关问题