OKWAVEのAI「あい」が美容・健康の悩みに最適な回答をご提案!
-PR-
解決
済み

アルゴリズム

  • すぐに回答を!
  • 質問No.112360
  • 閲覧数137
  • ありがとう数1
  • 気になる数0
  • 回答数3
  • コメント数0

お礼率 7% (1/14)

この問題も分かりません。

あるアルゴリズムの実行時間がO(NlogN)であり、別のアルゴリズムは(N~3)であるとする。
このことから2つのアルゴリズムの性能についてどのようなことがいえるか。

分かる方、よろしくお願いします。
通報する
  • 回答数3
  • 気になる
    質問をブックマークします。
    マイページでまとめて確認できます。

質問者が選んだベストアンサー

  • 回答No.1
レベル8

ベストアンサー率 58% (23/39)

まずはN(全体数)が10の場合を考えます。
そうすると、
O(10log10)=O(10)
(10~3)=(1000)

次にNが100の場合を考えます。
O(100log100)=O(100×2)=O(200)
(100~3)=(1000000)

上記からNが10倍になった時の状況は
O(NlogN)は20倍
(N~3)は1000倍になりました。
つまり全体数が大きくなるにつれてO(NlogN)の方が高性能であると言えます。

※log=log10としました。
お礼コメント
algorizum

お礼率 7% (1/14)

早速のご回答ありがとうございました。
大変申し訳ないのですが、問題が若干間違ってました。
O(NlogN) → N logN
(N~3) → O(N~3)
でした。
すいません。
答えに影響ありますか?
投稿日時 - 2001-08-01 17:34:34
-PR-
-PR-

その他の回答 (全2件)

  • 回答No.2
レベル8

ベストアンサー率 58% (23/39)

データ量増加に伴う判定回数の比率ですので、影響はありません。
データ量増加に伴う判定回数の比率ですので、影響はありません。


  • 回答No.3
レベル14

ベストアンサー率 30% (2593/8599)

O(NlogN)とO(N^3)なら文句なく前者に軍配です。O(N^3)型だとデータ数が増えるとパンクします。
O(NlogN)とO(N^3)なら文句なく前者に軍配です。O(N^3)型だとデータ数が増えるとパンクします。
このQ&Aで解決しましたか?
関連するQ&A
-PR-
-PR-
こんな書き方もあるよ!この情報は知ってる?あなたの知識を教えて!
このQ&Aにはまだコメントがありません。
あなたの思ったこと、知っていることをここにコメントしてみましょう。

その他の関連するQ&A、テーマをキーワードで探す

キーワードでQ&A、テーマを検索する
-PR-
-PR-
-PR-

特集


いま みんなが気になるQ&A

関連するQ&A

-PR-

ピックアップ

-PR-
ページ先頭へ