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

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

分かる方、よろしくお願いします。

A 回答 (3件)

まずは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としました。
    • good
    • 0
この回答へのお礼

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

お礼日時:2001/08/01 17:34

O(NlogN)とO(N^3)なら文句なく前者に軍配です。

O(N^3)型だとデータ数が増えるとパンクします。
    • good
    • 0

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

    • good
    • 0

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!


人気Q&Aランキング

おすすめ情報