アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。
Q&A
解決済
2回答
361閲覧
総合スコア105
0グッド
1クリップ
投稿2020/07/05 13:43
0
1
オーダー記法についてです。 100(n^3)logn=O((n^3)logn) 上記が正しいかどうかを確認したいです。
こちらのURLを見たら、logn=O(n)と書いてあったのでわからなくなりました。 lognがO(n)になるのなら問題の(n^3)lognは n^3*n=n^4だから、O(n^4) という形になるのでしょうか。
気になる質問をクリップする
クリップした質問は、後からいつでもMYページで確認できます。
またクリップした質問に回答があった際、通知やメールを受け取ることができます。
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
質問へのコメント
回答2件
ベストアンサー
オーダー記法には上界と下界とその両方を示すものの3種類があります。 そのPDFでは、定義上、上界のみを問題にしてるのでlogn=O(n)が正しいということになります。 同様に100(n^3)logn=O(n^4)も100(n^3)logn=O((n^3)logn)も正しいです。
投稿2020/07/05 13:59
総合スコア2047
回答へのコメント
2020/07/06 02:19
f(n)=O(g(n)) であるとは、nが大きくなった時、f(n)とg(n)の増え方を比較するとf(n)の方がg(n)よりも増え方が遅い、もしくは同じ程度であることを意味します。 log n = O(n)は、log n の方がnよりも増え方は遅いという意味になります。 グラフを書いてみたりすると、このことは容易に確認できます。 同様に、n^2やn^3よりもlog nの増え方が遅いので、 log n = O(n^2) log n = O(n^3) と表すこともできます。
投稿2020/07/05 14:24
総合スコア20669
あなたの回答
tips
太字
斜体
打ち消し線
見出し
引用テキストの挿入
コードの挿入
リンクの挿入
リストの挿入
番号リストの挿入
表の挿入
水平線の挿入
プレビュー
15分調べてもわからないことはteratailで質問しよう!
ただいまの回答率85.35%
質問をまとめることで思考を整理して素早く解決
テンプレート機能で簡単に質問をまとめる
オーダー記法の考え方がわかりません。
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2020/07/06 02:19