algorithm - 渐近符号中的非自反关系示例

Question

举个例子说明所有三个条件

f(n)!= O(g(n)),

f(n)!= Theta (g(n)) 和

f(n)!= 欧米茄 (g(n))

成立。

---

我们可以说振荡表示，即 sinx 或 cos x 可以适用于这个问题。但它会是反身关系吗？并且它也不是非负函数。那么，还有什么其他可能的例子呢？？

Answer 1

没有。这不可能。没有任何振荡函数，因为这种函数的周期是恒定的，您无法获得指定的结果!另外，如果 f(n) !=O(g(n)) , 绝对 f(n) = Omega(n) (可能是 Theta(n) )根据定义。我的意思是如果 f(n) != O(g(n)) , 然后 lim_{n \to infty} g(n)/f(n) = c < \infty .所以，这意味着 f(n) = Omega(g(n)) (如果 c > 0 ， f(n) = Theta(g(n) )。