アルゴリズム

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

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

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

No.1 ベストアンサー 回答者： ahsblue 回答日時： 2001/08/01 16:28

まずはＮ（全体数）が１０の場合を考えます。

そうすると、
Ｏ（１０ｌｏｇ１０）＝Ｏ（１０）
（１０~３）＝（１０００）

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

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

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

この回答へのお礼

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

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

No.3 回答者： ymmasayan 回答日時： 2001/08/01 23:34

Ｏ（ＮlogＮ）とＯ（Ｎ＾３）なら文句なく前者に軍配です。

Ｏ（Ｎ＾３）型だとデータ数が増えるとパンクします。

No.2 回答者： ahsblue 回答日時： 2001/08/01 17:50

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