algorithm - 如果 f ≠ ω(g)，是否 f = O(g)？

Question

我无法证明或反驳这个陈述:

If f ≠ ω(g), then f = O(g)

直觉上，我认为该陈述是错误的，但是，我无法找出有效的反例。

我的想法是，我们知道 f 不受 g 的函数的限制，但这并没有告诉我们关于上限的任何信息。

有什么想法吗？正确方向的提示？

Answer 1

提示一下，这个说法是错误的。想一想两个来回振荡的函数，其中每个函数一遍又一遍地超越另一个函数。这将使 f ≠ ω(g)，因为 f 反复被 g 支配，并且会使 f ≠ O(g)，因为 f 反复支配 g。

您需要找到使这项工作可行的 f 和 g 的具体选择，并正式确定 f ≠ ω(g) 和 f ≠ O(g) 以将其形式化，我将把它留作练习。

希望这对您有所帮助!