漸近表記-n（log n）（log n）は単純化されますか？

Question

n個のlog nステップを取るアルゴリズム（例：ヒープソート）で、ステップがlog n時間かかる（例：<！> quot; big <！> quotの比較/交換; 0からnの範囲の整数-1）、プロセス全体の漸近境界は何ですか。

明らかに<！> quot; n（log n）（log n）<！> quot;と言うことはできますが、これを<！> quotに単純化できないと自分自身を納得させるのは大変です。 n log n <！> quot;。同時に、私ができると主張する本能を正当化するのに苦労しています。

本能はこれに関して単純に間違っているのですか？

編集

複雑な問題を避けるための私の簡単な例が問題を複雑にしているようです。まあ。

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

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

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

編集

<！> quot; n（log n）（log n）<！> quot;間違っています。

aがO（b log b）で、bがO（log c）の場合、cに関してaとは何ですか

Answer 1

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

関数f（n）= n（log n）（log n）としましょう。 theta（n log n）であると考えると仮定します。つまり、f（n）<！> lt; = a * n log nが大きいnに対して成り立つaがあります。

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関数ではありません。

Answer 2

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

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

Answer 3

単に一定の係数による削減ではないため、n (log n) (log n)をn (log n)に削減することはできません。

2 ^<=> の何が問題になっていますか？

Answer 4

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

  

Complexity O（f（n））は、cが存在することを意味します。これにより、終了する前の対応するチューリングマシンのステップ数がc * f（n）以下になります。nは入力。

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

しかし、チューリングマシンを直接プログラミングしていれば、あなたの質問は発生しなかったでしょう。現実の世界では、抽象化することを好みます。まだ<！> quot; steps <！> quot;を計算しますが、プログラムを実行するために必要なものであるため、特定の操作は 1つのステップを取ると想定しています。さまざまな理由でそれを想定しています：

• 各32ビット整数の加算が実際に1ステップであるCPUの実際の動作に似ている場合があります（実際にそれを悪用するアルゴリズムが存在します。たとえば、<！> quot; bit-verctor dominators <！> quot;）。 。
• 同じドメイン内の異なるアルゴリズムを比較します（たとえば、比較回数を測定して配列の並べ替えを比較します）。

この場合（最初のEDIT）、複雑さの尺度を具体化する場合は、Oの下で関数を乗算する必要があります。1つのステップを取ると考えていたものがO（log N）ステップを取ると考えられる場合、具体化されたステップの量は、O（log N）倍に増加します。したがって、総複雑度はO（N log N log N）です。

---

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