アルゴリズムの計算量問題で、

解決済

質問者：unicornix
質問日時：2009/07/05 05:07
回答数：1件

今、大学でアルゴリズムのクラスをとっているのですが、
教科書を読んでいて、感覚的には理解できているのですが、それを証明するとなるとどうしたらいいのか分からないところがあり、困っています。
それは、
2つの入力関数のうち、おおきい方を出力する関数をmax()、小さい方を出力する関数をmin()とするとき、
(1). max(f(x),g(x))=Θ(g(x)+f(x))は正しいか？
(2). min(f(x),g(x))=Θ(g(x)+f(x))は正しいか？
という問題なのですが、

1に関して言えば、
f(x)≦max(f,g)　かつ　g(x)≦max(f,g)　故に　f(x)+g(x)≦2max(f,g)
よって、定数1/2を掛けたf(x)+g(x)によってmax(f,g)は下から抑えられるため、max(f(x),g(x)) = Ω(f(x)+g(x)).
また、max(f,g)は大きいどちらかの関数を選ぶため、f(x)かg(x)
故にmax(f,g)≦f(x) + g(x)
よって、定数1を掛けたf(x)+g(x)によってmax(f,g)は上から抑えられるためO(f(x)+g(x)).
従って、Ω(f(x)+g(x))かつO(f(x)+g(x))より、max(f(x),g(x))=Θ(g(x)+f(x)).
といった感じで1.の方は証明できると思います。

2.の問題では、O(f(x)+g(x))であるが、Ω(f(x)+g(x))にならないことを示せばいいと思うのですが、
1.と同様に、f(x)≧min(f,g)　かつ　g(x)≧min(f,g)　故に　f(x)+g(x)≧2min(f,g)
よって、定数1/2を掛けたf(x)+g(x)によってmax(f,g)は上から抑えられるため、max(f(x),g(x)) = O(f(x)+g(x)).と漸近的上界を求めることはできるのですが、
漸近的下界を反証する方法が思いつきません。

アドバイスをいただければ大変助かります。
よろしくお願いします。