ログイン 新規登録

お使いのブラウザ(Internet Explorer)では閲覧、ログイン、質問の作成や回答などに不具合が生じることがございます。
誠に恐れ入りますが、下記の推奨ブラウザをご利用くださいませ。

推奨ブラウザ:Google Chrome(グーグル・クローム)

2つの関数の順番を決める場合...

■考えている内容や答え
以下の関数の計算複雑度を表すオーダーを考え、その速さの順序を明らかにしようとしています。

■特に不安な点や、確認したいこと
2^(logn) = O(n)
8n+1 = O(n)
ですが、2つの関数の順番を決める場合、8n+1の方が2^(logn) よりも遅いという理解で合っていますか。
間違っていたら、正しい答えを教えてください。

回答(1件)

ベストアンサーに選ばれました
オンライン家庭教師

2^logn=(e^log2)^logn

=e^(log2×logn)

=(e^logn)^log2

=n^log2

なので

2^logn=O(n^log2)

です。

log2<1なので、8n+1の方が早いです。

この回答をした先生に
オンラインでの個別指導を依頼できます

tamu
オンライン家庭教師

自己紹介

愛媛県で田村学習塾という塾を経営しています。 どんな些細な質問にも丁寧に答えます。 個別質問は対応...

合格実績

塾講師、家庭教師として7年目
  • 2^(√(logn)) = O(n)

    と考えており2^(logn) = O(n)と至りましたが、そもそも2^(√(logn)) = O(n)も間違えているのでしょうか。

    11か月前
  • 2^√logn≠O(n)

    です。


    https://ja.m.wikipedia.org/wiki/%E3%83%A9%E3%83%B3%E3%83%80%E3%82%A6%E3%81%AE%E8%A8%98%E5%8F%B7

    の厳密な定義などを確認してください。

    11か月前

    tamu

    オンライン家庭教師
  • 確認しましたが、それでは2^√logn = O(2^n)でしょうか。

    11か月前
  • なぜでしょうか?

    11か月前

    tamu

    オンライン家庭教師
  • まちがえました。O(2^logn)でしょうか。ルートを省略した場合ですが、オーダー記法ではどこまで省略していいのかわかりません。

    11か月前
  • ルートも基本的には勝手に省略はできません。

    O(√n)≠O(n)

    です。


    8n+1=O(n)

    も勝手に8や+1を省略しているわけではなく

    lim[n→∞](8n+1)/n=8

    で有限な値に収束しているからです。

    11か月前

    tamu

    オンライン家庭教師
  • ごめんなさい。

    少し勘違いしていた部分がありました。


    2^logn/nや2^√logn/2^lognも有限な値に収束するので

    2^logn=O(n)

    2^√logn=O(2^logn)

    √n=O(n)

    も間違いではなかったですが、大きさを評価する時には少し過大になっていることだけ注意が必要です。

    11か月前

    tamu

    オンライン家庭教師
回答へコメントする
あなたがベストアンサーに選んだ
tamu
さんはオンライン家庭教師をしています

他の質問・回答も見る