渐近符号

Question

这是渐近表示法的一个问题，是麻省理工学院OpenCourse导论对算法的分配。

对于下面每条语句，决定它是总是真，从不真，还是对于渐近非负函数f和g，有时是真。如果是总是真还是从不真E 211，解释原因。如果它是有时是真，那么给出一个它是真的例子，以及一个它是假的例子。

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)||就像向量范数。

Answer 1

第一个是不正确的:从这个f(n) ≠ O(g(n))，它没有遵循这个：f(n) = w(g(n))。这两个函数可能会在某个点相交，然后扇一个位置，另一个变得更大(如果我使用简单的单词)。

他们选择的函数就是这样的:对于n <= 1，第一个f(n) > g(n)，并且存在ns，其中g(n) > f(n) (例如g pi / 2)。

Answer 2

我认为n*sin(n)只是表明它是一个不断变大的函数&对于随后的n值，甚至对于用于定义大O&因此f(n) ≠ O(g(n)) and g(n) ≠ O(f(n))的常数乘法器的所有选择，它都比f(n) = 1小。

像g(n) = 2*sin(n)这样天真选择的函数在这里做不到什么。人们可能会认为，这也会保持f(n) = 1的交替，但g(n) = O(f(n)) : M*f(n) > g(n) for M = 3等。