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

Question

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

Answer 1

没有。

我认为您的问题等同于:给定函数 f 和 g，f 是 O(g) 或 g 是 O(f) 是否总是正确的？这在 SE Computer Science 问题中得到了回答 Are the functions always asymptotically comparable? .如果 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) 中。