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

質問

今、大学でアルゴリズムのクラスをとっているのですが、
教科書を読んでいて、感覚的には理解できているのですが、それを証明するとなるとどうしたらいいのか分からないところがあり、困っています。
それは、
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)).と漸近的上界を求めることはできるのですが、
漸近的下界を反証する方法が思いつきません。

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

回答No.1

Tacosan · ベストアンサー

「=」を示すためにはきちんと証明しなければなりませんが, 「=」でないことを示すには反例が 1つあれば OK.

お礼

返事をしたつもりでいました。
その方法で無事簡単に答えることができました。
どうもありがとうございます。