algorithm - 在渐近符号中，给定 g(n)，O(g(n)) 和 Ω(g(n)) 的并集是否是所有函数的全集 U？

Question

似乎是的。任何直观或严肃的证据都值得赞赏。

Answer 1

不。

我认为您的问题与此等价：给定函数 f 和 g，f 是 O(g) 还是 g 是 O(f) 是否总是正确的？这在 SE 计算机科学问题中得到了回答，这些函数是否总是渐近可比的？. 如果 f 和 g 不能通过 big-O 进行比较，则 f 不在 O(g) 中，f 也不在 big-Omega(g) 中。

例如，以上面 SE 问题的最高答案：定义 f(n) = n，并定义 g(n) = 1（如果 n 是奇数），n^2（如果 n 是偶数）。不管你走多远，有时 f 比 g 大得多，有时 g 比 f 大得多。所以 f 既不在 O(g) 也不在 big-Omega(g) 中。