証明問題

質問

以下について真偽を証明せよ。（偽の場合は反例を挙げよ。）
※Oはビッグ・オー、Ωはビッグ・オメガ、Θはビッグ・セータ。

（１）もしf(x)=O(g(x))が成り立つなら、g(x)=Ω(f(x))も成り立つ。
OとΩは丁度逆の定義なので自明で真のような気がしますが、あえて定義から証明しようとすると、f(x)=O(g(x))ということは、f(x)<=C*(g(x)) x>kとなるような定数Cとkが存在し、また、g(x)=Ω(f(x))ということは、g(x)>=C*(f(x)) x>kとなるような定数Cとkが存在する、となってこの先の導き方がわかりません。ひょっとしてこれは偽でしょうか？

（２）β>0のとき、Θ(β(f(x)))=Θ(f(x))。
私が問題文の意味を聞くのもなんですが、ΘとはOかつΩのことなので、これは（１）β(f(x))=O(f(x))かつβ(f(x))=Ω(f(x))と、（２）(f(x))=O(β(f(x)))かつ(f(x))=Ω(β(f(x)))の二つを証明すればよいということなのでしょうか？

回答No.1

Tacosan · ベストアンサー

(1): f(x) = O(g(x)) ということは, 「正定数 c, M が存在し, 全ての x ≧ M に対し f(x) ≦ c g(x)」です. で, g(x) = Ω(f(x)) は「正定数 c, M が存在し, 全ての x ≧ M に対し g(x) ≧ x f(x)」ですね. ここで O(・) の定義にある c や M を使って Ω(・) の定義の c や M が作れれば命題は真だし, そうでなければ (おそらく) 偽.
(2): そうです.

お礼

有り難うございます。
（１）については、f(x)<=C*(g(x)) x>Mとなるような正定数CとMが存在する場合、正定数(1/C)をf(x)にかければ大小関係は維持出来ると思います。g(x)>=(1/C)*(f(x)) x>M。　したがって、真と考えましたが正しいでしょうか。
（２）については、β(f(x))=O(f(x))かつβ(f(x))=Ω(f(x))ということはβ(f(x))<=C*(f(x))かつβ(f(x))>=C*(f(x))。βとCが定数である以上、βとCを入れ替えれば大小関係は逆になるので成り立つ。
また、(f(x))=O(β(f(x)))かつ(f(x))=Ω(β(f(x)))ということは(f(x))<=C*(β(f(x)))かつ(f(x))>=C*(β(f(x)))。これもβとCが定数である以上、βとCを入れ替えれば大小関係は逆になるので成り立つ、したがって真と考えましたが正しいでしょうか。

回答No.2

Tacosan

(1) はおよそそれでいいけど, もう少し丁寧にいくなら
f(x) = O(g(x)) なので, うまく正定数 c, M を選べば任意の x ≧ M に対し f(x) ≦ c g(x). つまり g(x) ≧ (1/c) f(x) となるので, c' = 1/c, M' = M とおけば任意の x ≧ M' に対し g(x) ≧ c' f(x). 従って g(x) = Ω(f(x))
とするところかな.
(2): あ～, すみません, 勘違いしてました.
この式は「g(x) = Θ(β f(x)) であるような任意の関数 g(x) は g(x) = Θ(f(x)) を満たす」という意味です. だから「g(x) = Θ(β f(x))」を仮定して「g(x) = Θ(f(x))」を示さないとダメです.

お礼

有り難うございます。
（１）については理解致しました。
（２）についてですが、正定数c1のときにg(x)<=c1*(β(f(x)))を満たし、正定数c2のときにg(x)>=c2*(β(f(x)))を満たす場合、今度は正定数をそれぞれc1*β、c2*βという値にしてあげれば定数βがなくても同じ意味になると思います。すなわちg(x)=O(f(x)) when c3=c1*β、g(x)=Ω(f(x)) when c4=c2*β。したがって真だと思われますが、正しいでしょうか。