2

アルゴリズムクラスのマスター定理を調べています。1つの問題として、nlognと1を比較して、MTのどちらのケースに該当するかを判断しようとしています。しかし、私はどちらが大きいかを理解するのに苦労しています。

編集：これは再発の問題を解決するためのものです。方程式はT（n）= 2T（n / 4）+ N*LogNです。それが役立つ場合に備えて、これを投げただけです。

4

2 に答える 2

1

このように考えてください：

  • O(N*LogN)は、どんなに大きくても、よりも大きい値を見つけることができるNように増加します。XNN*LogNX
  • O(1)何Nがあっても同じままになります。

これは、漸近的O(1)に優れていることを意味します。つまり、一部の（おそらく非常に高い）値の場合は遅くなります。NO(N*LogN)

于 2013-02-19T01:51:33.127 に答える
0

アルゴリズムがO（NlogN）の場合、これは数値Aと実行時間Bの量が存在することを意味し、Aより大きい入力サイズNの場合、実行時間はNlogNのB倍未満になります。

アルゴリズムがO（1）の場合、入力サイズに関係なくアルゴリズムの完了が保証される一定の時間Cが存在することを意味します。

1つがO（NlgN）でもう1つがO（1）である2つのアルゴリズムを比較すると、一般に、十分に大きいNの値に対してO（1）アルゴリズムの方が高速であることがわかりますが、多くの場合、 Nの値が小さい場合、O（NlgN）アルゴリズムの方が高速になる可能性があります。

実際、O（N ^ 3）またはO（N ^ 4）アルゴリズムのようなものは一般にかなり悪いように見えますが、Nが通常の場合、O（N ^ 4）アルゴリズムでさえO（1）アルゴリズムよりも優れている可能性があります。少数（たとえば、1〜5程度）で、非常に大きくなることはありません（50の値がときどきある場合でも、パフォーマンスが大幅に低下する可能性があります）。

于 2013-02-19T02:15:14.997 に答える