質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.84%

  • アルゴリズム

    357questions

    アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

オーダー記法の証明について

解決済

回答 1

投稿

  • 評価
  • クリップ 0
  • VIEW 172

BitCoin

score 40

問題
O(2^n) ≠ O(3^n) を証明せよ

この問題なのですが、さっぱりわからずお手上げ状態です。
どなたか証明の仕方をご教授してくださる方いないでしょうか

対数を使うのかなとは思いましたがそこから手も足もでません・・・

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • swordone

    2018/05/20 21:33

    2と3が逆ならわかるけど…

    キャンセル

  • BitCoin

    2018/05/20 21:38

    といいますと?

    キャンセル

  • HogeAnimalLover

    2018/05/20 22:34 編集

    逆でもこのままでも同じですよ。 以下追記。失礼、ランダウの記号を集合でなく関数と解釈すると逆のみ成立しますね。私は集合と解釈しました。

    キャンセル

回答 1

checkベストアンサー

+4

 まずは基本ですが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 21:47 編集

    昨日
    https://teratail.com/questions/126980
    で回答してもらいありがとうございます。
    集合という概念は分かります。しかし、なぜそしてO(3^n)にO(2^n)が含まれているかわからず・・・
    O(2^n)の要素でないものを一つ以上提示すれば証明終了とありますが、二次関数が一次関数に含まれている場合はn^2 >=n を変形してCを出すのですが
    今回はどのようにすればこのCの値を求めることができるのかわからず・・・・

    キャンセル

  • 2018/05/20 21:46

    質問はn^2ではなくて2^nですよ。

    キャンセル

  • 2018/05/20 21:48

    おっと、失礼しました。編集しなおします。

    キャンセル

  • 2018/05/20 22:14

    ありがとうございます。
    cを確定した場合、nを充分大きい値にすれば左辺は右辺よりも大きくなってしまう→f(n) = 3 ^nはo(2^n)の要素ではない
    このつながりがいまいち理解できません。
    もしよろしければ具体例など挙げて説明してもらえないでしょうか・・

    キャンセル

  • 2018/05/20 22:29

    それは「ε-δ論法」で議論するのが一般的では?
    https://ja.m.wikipedia.org/wiki/イプシロン-デルタ論法
    任意のnに対して、あるn1が存在してC2^nでは抑えることができない、というような。
    数学の基礎的な概念を抑えてある以外に議論する方法があるのであれば是非知りたく。

    キャンセル

  • 2018/05/20 22:40

    もちろん、厳密にいえばε-δ論法が必要です。が、それはそもそもオーダーの定義がどのようにされているか次第です。前回の質問を見た限り、オーダーの定義自体かなり曖昧な理解であったようなので、この形で説明しました。

    まあオーダーの定義をそもそもしっかり学ぶべきなのでしょうけど。

    キャンセル

  • 2018/05/20 22:47 編集

    失礼しました。
    BitCoinさんの具体例ということに対してのコメントのという意図でした。

    一応反例を挙げることは可能ですが、厳密な証明にはオーダーの定義がしっかりしていることが必要であることには同意です。

    キャンセル

  • 2018/05/20 22:59

    僕が余計なことを言ったばかりに、すいません。
    オーダーの定義は
    1.影響力が一番強い項以外無視する
    2.定数倍の差は無視する(係数は書かない)ですよね。
    HogeAnimalLoverさんの証明の方法は理解できました。
    ただ一つ気になるところがあり
    cはnよりも先に確定しなければならない
    この、先に確定するかしないかということから要素を満たす満たさないというものは何かの公理?定理?定義?なのでしょうか?

    キャンセル

  • 2018/05/20 23:05

    オーダーの定義としてそれは不適切です。影響力の弱い項や係数を書いてはいけないという決まりなど存在しません(もちろん、不要ではありますがどちらでも良い、そこは本質ではありません!)。まず定義を学びなおしてください。

    キャンセル

  • 2018/05/20 23:31

    ありがとうございます。
    定義について目を通しました。
    T(n) = O(f(n))
    ⇔ ある実数c>0と自然数n0が存在して全てのn≧n0に対してT(n)≦cf(n)
    が成り立つ
    そういうことだったんですね。すいません。定義というものを勘違いしていました。
    確かにオーダーの定義からCをいつ決めても(n)≦cf(n)とならなければならないのに
    今回の場合はそうとは限らないですね。

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 90.84%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る

  • アルゴリズム

    357questions

    アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。