1

这是MIT OpenCourse Introduction to Algorithm作业中关于Asymptotic Notation的问题：对于以下每个陈述，确定对于渐近非负函数f和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)) (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)||看起来像矢量规范。

4

2 回答 2

3

我认为n*sin(n)只是表明它是一个函数，即使对于用于定义 Big O的常数乘数f(n) = 1的所有选择，它都比 n 的后续值不断变大和变小，因此f(n) ≠ O(g(n)) and 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等等

于 2012-02-18T12:53:05.587 回答
2

第一个是不正确的：从这里f(n) ≠ O(g(n))它不遵循这个：f(n) = w(g(n))。这两个功能可能在某个点相交，然后拍打位置，另一个变得更大（如果我使用简单的话）。

他们选择的函数就是这种情况：对于 n <= 1，第一个 f(n) > g(n) 并且存在 g(n) > f(n) 的 ns（例如 pi / 2）。

于 2012-02-18T12:24:28.903 回答