ログイン 新規登録

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

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

以下の関数の計算複雑度を表すオーダーを考...

■考えている内容や答え
以下の関数の計算複雑度を表すオーダーを考え、その速さの順序を明らかにしようとしています。
8^n + 5n = O(8^n)
n^(2logn-4) = O(n^logn)

8^n + 5nの方がn^(2logn-4)よりも早いと考えていますが合っていますか?
間違えていたらその理由と共にご指摘願いたいです。

■特に不安な点や、確認したいこと
2^logn=O(n)
2^√logn=O(2^logn)
n^(2logn-4) = O(n^n)


仮数部が定数ならオーダは定数倍もしくはnで済みますが、仮数部がnだと指数関数になり、遅くなるという理解です。
manabu さんの質問 勉強レベル4
3か月前

回答(1件)

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

8^n

=e^(nlog8)


n^(2logn-4)=e^{(2logn-4)logn}


nlog8=O(n)

(2logn-4)logn=O((logn)^2)

なので、nlog8の方が早く、8^n+5nの方が早いです。

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

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

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

  • この質問と似た質問

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