今、大学でアルゴリズムのクラスをとっているのですが、
教科書を読んでいて、感覚的には理解できているのですが、それを証明するとなるとどうしたらいいのか分からないところがあり、困っています。
それは、
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)).と漸近的上界を求めることはできるのですが、
漸近的下界を反証する方法が思いつきません。
アドバイスをいただければ大変助かります。
よろしくお願いします。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 数学 原始関数の存在性の証明について 数学科の3回生です。院試の勉強でつまづいたので助けてほしいです。 R 6 2022/11/13 19:19
- 数学 代数学 環 1 2022/10/12 17:29
- 数学 ほんとに何度もすみません。 どうか相手にしてください。 逆関数というのは、「出力と入力の関係式を逆に 16 2023/08/25 20:45
- 数学 f(x)=2x+∮(0~1)(x+t)f(t)dt を満たす関数f(x)を求めよ。 3 2022/07/05 22:54
- 数学 高校数学で質問があります。 2 2023/02/13 16:40
- 高校 合成関数の問題です。FG例題128番について 4 2023/07/15 17:31
- 数学 微分の意味ついて質問が有ります 4 2023/04/05 23:17
- 数学 確率について ①Xが実数値をとる確率変数で、f(x)=0(x<=-1),1/4x+1/4 (-1<= 2 2022/06/20 18:44
- 数学 連続であることを示すときの最後のεについて 6 2023/04/14 23:00
- 数学 1次関数の最大と最小 9 2023/03/17 09:58
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
級数の係数を求める
-
YouTuberでサトマイっていう人...
-
研究室でちょっとういてる?
-
数学II この問題の②について co...
-
(3)のグラフがなぜこうなるの...
-
黄色の式が極値を持ちそれが極...
-
数学II θの範囲に制限がないと...
-
皆さんが高校数学で、一番感動...
-
必要条件 十分条件について
-
次の空欄に当てはまるものを以...
-
以前にも質問させていただいた...
-
微分係数の定義?
-
∫1/lnxdx について
-
連続を示す必要ありますか
-
命題がわかりません!!
-
複素数平面
-
数学II AB=2である2定点A,Bに対...
-
(3)なのですが、どうやら正...
-
行列のべき乗昨日
-
フーリエ変換の相似性(時間軸...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
整数問題 兎に角 難問です 千葉...
-
過去質『すべての自然数とすべ...
-
確率の問題 数学と実生活と
-
微分がムズいです。 新高二です...
-
逆関数の合成関数について質問...
-
初歩的な計算式の問題です。
-
下の画像の中の三角形は正方形...
-
全然わからないので質問する資...
-
a(n)=1/(n+1)! lim[z->π/2](d/d...
-
画像において、質問がございま...
-
虚数の計算を教えてください
-
三角関数の変換で納得いかない...
-
計算手順について
-
過去に 「ii) f(z)=1/(z^2-1) r...
-
数学を勉強すると論理的思考力...
-
【数学・標準偏差σ】標準偏差の...
-
計算式の答えまでの過程を教え...
-
おしえてgooに図形の問題を投稿...
-
こちらの式はtan(z)のローラン...
-
ほんとになんでうごくかわからない
おすすめ情報