Q&A
2と3が逆ならわかるけど…
問題
O(2^n) ≠ O(3^n) を証明せよ
この問題なのですが、さっぱりわからずお手上げ状態です。
どなたか証明の仕方をご教授してくださる方いないでしょうか
対数を使うのかなとは思いましたがそこから手も足もでません・・・
回答1件
0
ベストアンサー
まずは基本ですがO(2^n)もO(3^n）も集合です。
そしてO(2^n) ⊂ O（3^n)です。ここまでは自明ですよね。あとはO（3^n)の要素であり、O（2^n)の要素でないものを一つ以上提示すれば証明終了です。
例えば、f(n) = 3^nを考えてみましょう。これは明らかにO(3^n)の要素です。それではO(2^n）の要素でしょうか？仮にO(2^n)の要素であると仮定します。すると以下の条件が満たされることになります。
**3 ^ n <= c * (2 ^ n) **
ただし、c,nはともに正の数であり、cはnよりも先に確定しなければならない
この条件式の両辺は明らかにプラスの数です。両辺からプラスの数(2 ^ n)を割ります。すると次の式が得られます。
**(3 ^ n) / (2 ^ n) <= c **
この式のcはnよりも先に確定できません。cを確定した場合、nを充分大きい値にすれば左辺は右辺よりも大きくなってしまいます。
以上からf(n) = 3 ^nはo(2^n)の要素ではないと言えました。
以下、質問がありましたので追記します。
(3 ^ n) / (2 ^ n) = (3 / 2) ^ n <= cですので
f(n) = 3^nがO(2^n)の要素である条件は結局次の形にまで変形できます。
n <= log c (底は3/2)
c,nはともに正の数であり、cはnよりも先に確定しなければならない
この条件を満たせないことは自明です。cを先に確定した場合n = 1+ log c (底は3/2）とすれば不等号が逆転します。つまり、**f(n) = 3^nがO(2^n)の要素である条件は満たされない。**といえます。
投稿2018/05/20 12:38
編集2018/05/20 13:26
総合スコア4830
昨日
https://teratail.com/questions/126980
で回答してもらいありがとうございます。
集合という概念は分かります。しかし、なぜそしてO(3^n)にO(2^n)が含まれているかわからず・・・
O（2^n)の要素でないものを一つ以上提示すれば証明終了とありますが、二次関数が一次関数に含まれている場合はn^2 >=n を変形してCを出すのですが
今回はどのようにすればこのCの値を求めることができるのかわからず・・・・
質問はn^2ではなくて2^nですよ。
おっと、失礼しました。編集しなおします。
ありがとうございます。
cを確定した場合、nを充分大きい値にすれば左辺は右辺よりも大きくなってしまう→f(n) = 3 ^nはo(2^n)の要素ではない
このつながりがいまいち理解できません。
もしよろしければ具体例など挙げて説明してもらえないでしょうか・・
それは「ε-δ論法」で議論するのが一般的では？
https://ja.m.wikipedia.org/wiki/イプシロン-デルタ論法
任意のnに対して、あるn1が存在してC2^nでは抑えることができない、というような。
数学の基礎的な概念を抑えてある以外に議論する方法があるのであれば是非知りたく。
もちろん、厳密にいえばε-δ論法が必要です。が、それはそもそもオーダーの定義がどのようにされているか次第です。前回の質問を見た限り、オーダーの定義自体かなり曖昧な理解であったようなので、この形で説明しました。
まあオーダーの定義をそもそもしっかり学ぶべきなのでしょうけど。
失礼しました。
BitCoinさんの具体例ということに対してのコメントのという意図でした。
一応反例を挙げることは可能ですが、厳密な証明にはオーダーの定義がしっかりしていることが必要であることには同意です。
僕が余計なことを言ったばかりに、すいません。
オーダーの定義は
1．影響力が一番強い項以外無視する
2．定数倍の差は無視する（係数は書かない）ですよね。
HogeAnimalLoverさんの証明の方法は理解できました。
ただ一つ気になるところがあり
cはnよりも先に確定しなければならない
この、先に確定するかしないかということから要素を満たす満たさないというものは何かの公理？定理？定義？なのでしょうか？
オーダーの定義としてそれは不適切です。影響力の弱い項や係数を書いてはいけないという決まりなど存在しません（もちろん、不要ではありますがどちらでも良い、そこは本質ではありません！）。まず定義を学びなおしてください。
ありがとうございます。
定義について目を通しました。
T(n) = O(f(n))
⇔ ある実数c>0と自然数n0が存在して全てのn≧n0に対してT(n)≦cf(n)
が成り立つ
そういうことだったんですね。すいません。定義というものを勘違いしていました。
確かにオーダーの定義からCをいつ決めても(n)≦cf(n)とならなければならないのに
今回の場合はそうとは限らないですね。
あなたの回答
tips
プレビュー
