1

n log nステップをとるアルゴリズム（ヒープソートなど）があり、ステップがlog n時間かかる場合（0からn-1の範囲の「大きな」整数の比較/交換など）、プロセス全体。

言うまでもなく「n（log n）（log n）」と言えますが、これを「nlogn」に単純化できないことを納得させるのに苦労しています。同時に、私は自分ができると主張する本能を正当化するのに苦労しています。

私の本能はこれについてまったく間違っていますか？

編集

問題を複雑にすることを避けるための私の単純な例が問題を複雑にしているようです。しかたがない。

質問の本当の理由は、私はしばしば既知の複雑さを持つ標準アルゴリズムを持っていますが、異なる基礎となるコンテナーを使用して実装されているため、個々のステップはO（1）ではなくO（log n）であるということです。たとえば、Hopcroftsオートマトン最小化アルゴリズムはO（n log n）ですが、状態、遷移、および中間結果にバイナリツリーコンテナを使用し始めると、ステップ自体がO（log n）になります-O（n log n）はO（1）アクセスの仮定が無効であるため、無効になりました。

それでも、人々はn個の状態とm個の遷移があると主張しますが、遷移注釈の数が一定であり、オートマトンが多かれ少なかれ決定論的であると仮定すると、nとmはオートマトンに対して線形に関連する傾向があります。

私は過去にこれについてあまり心配していませんでした-私が扱っているケースはそれほど大きくありません。しかし、まあ、私はオートマトンコードの主要なリファクタリングを行っており、いくつかの主要なアルゴリズムについては、計算を適切に行う方がよいと思いました。

編集

また、「n（log n）（log n）」が間違っていると私はますます確信しています。

aがO（b log b）であり、bがO（log c）である場合、cに関してaは何ですか？

4

4 に答える 4

5

一般に、このような複雑さを乗算することはできません。ヒープソートの場合、Nはヒープ内のアイテムの数を示しますが、大きな整数の場合、Nはおそらく可能な値の上限を示します。一般に、これらは関連している必要はないので、むしろN log N log M（Mはアイテムが取る可能性のある範囲）です。

特定のアプリケーションでは、ほとんどの場合、大きな整数は特定の分布に従います。たとえば、それらがすべて10^20未満であることがわかっている場合があります。その場合、比較操作には一定の時間がかかります（10 ^ 20の上限によって決定されます）。次に、log Mも一定であり、全体の複雑さはO（N log N）になります。

于 2009-10-25T05:40:09.700 に答える
3

これが矛盾による証明です：

関数だとしましょうf(n) = n(log n)(log n)。Θ(n log n)それも、、であると考えると仮定します。theta(n log n)つまり、大きいa場合にf(n) <= a * n log n当てはまるforがありますn。

今考えてみましょうf(2^(a+1))：

f(2^(a+1)) = 2^(a+1) * log(2^(a+1)) * log(2^(a+1)) = 2^(a+1) * log(2^(a+1)) * (a+1)、これは明らかにより大きくa * 2^(a+1) * log(2^(a+1))、矛盾があります。したがってf(n)、関数ではありませんn log n。

于 2009-10-25T05:54:28.080 に答える
2

それが一定の要因による削減ではないという理由だけで、に削減n (log n) (log n)することはできません。n (log n)

何が問題なのn (log n)2ですか？

于 2009-10-25T05:37:18.333 に答える
1

さて、プログラムの一般的な複雑さの尺度は次のとおりです。

複雑さO（f（n））は、終了する前の対応するTuringマシンのステップ数がc * f（n）以下であるような存在を意味しcます。ここで、nは入力の長さです。

この定義では、整数は任意に大きくなる可能性があり、それらに対する算術演算もO（n）の下での関数を増やすため、すべてが考慮されます。

しかし、チューリングマシンを直接プログラミングしていれば、あなたの質問は起こらなかったでしょう。現実の世界では、抽象化することを好みます。プログラムの実行に必要な「ステップ」を計算しますが、特定の操作は1ステップであると想定しています。さまざまな理由により、次のように想定しています。

  • これはCPUの実際の動作に似ている可能性があり、各32ビット整数の加算は実際に1ステップです（実際にそれを悪用するアルゴリズム、たとえば「ビットバークタードミネーター」が存在します）。
  • 同じドメイン内のさまざまなアルゴリズムを比較します（たとえば、比較の数を測定して配列の並べ替えを比較します）。

この場合（最初の編集）、複雑さの尺度を具体化する場合は、Oの下で関数を乗算する必要があります。1つのステップを実行すると考えたものがO（log N）ステップを実行すると見なされた場合、具体化された量ステップはO（log N）の係数で増加します。したがって、全体の複雑さはO（N log N log N）です。

2番目の編集に関しては、それは別の状況です。アルゴリズムをO（n log N）の複雑さとします。ただし、入力はM数字と各log K桁で構成されているため、 `N = O（M log K）（区切り文字などを考慮する必要があります）。全体的な複雑さをO（M * log K *（log M + log log K））と書くのは数学的に正しいので、ここでは問題はありません。しかし、通常、比較するさまざまなアルゴリズムの共通の基礎を見つけるために、不要な詳細を抽象化します。

于 2009-10-25T07:47:45.950 に答える