アルゴリズム

質問

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

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

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

回答No.1

ahsblue · ベストアンサー

まずはＮ（全体数）が１０の場合を考えます。
そうすると、
Ｏ（１０ｌｏｇ１０）＝Ｏ（１０）
（１０~３）＝（１０００）

次にＮが１００の場合を考えます。
Ｏ（１００ｌｏｇ１００）＝Ｏ（１００×２）＝Ｏ（２００）
（１００~３）＝（１００００００）

上記からＮが１０倍になった時の状況は
Ｏ（ＮｌｏｇＮ）は２０倍
（Ｎ~３）は１０００倍になりました。
つまり全体数が大きくなるにつれてＯ（ＮｌｏｇＮ）の方が高性能であると言えます。

※ｌｏｇ＝ｌｏｇ１０としました。

お礼

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

回答No.3

ymmasayan

Ｏ（ＮlogＮ）とＯ（Ｎ＾３）なら文句なく前者に軍配です。Ｏ（Ｎ＾３）型だとデータ数が増えるとパンクします。

回答No.2

ahsblue

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