ログイン 新規登録

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

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

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

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

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

回答(1件)

ベストアンサーに選ばれました
個人家庭教師

2^logn=(e^log2)^logn

=e^(log2×logn)

=(e^logn)^log2

=n^log2

なので

2^logn=O(n^log2)

です。

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

  • 2^(√(logn)) = O(n)

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

    3か月前
  • 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

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

    3か月前

    tamu

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

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

    3か月前

    tamu

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

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

    O(√n)≠O(n)

    です。


    8n+1=O(n)

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

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

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

    3か月前

    tamu

    個人家庭教師
  • ごめんなさい。

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


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

    2^logn=O(n)

    2^√logn=O(2^logn)

    √n=O(n)

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

    3か月前

    tamu

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

累計17,000問以上の質問から、あなたがわからない問題・回答を写真で検索しよう!

あなたと同じ問題を探そう
写真で検索する

  • この質問と似た質問

  • あなたと同じ問題を探そう
    写真で検索する