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 comparison?で回答されています。. 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) でもありません。