対数対二人の対数時間の複雑さ

cs.stackexchange https://cs.stackexchange.com/questions/654

質問

実際のアプリケーションでは、$ mathcal {ol（n））$を$ mathcal {o}（ log（n））$を使用する場合、具体的な利点があります。

これは、より従来のバイナリ検索ツリーの実装ではなく、たとえばVan Emde Boasの木を使用する場合です。しかし、たとえば、$ n <10^6 $を取る場合、最良の場合、二重対数アルゴリズムは対数1を（約）$ 5 $の係数よりも上回ります。また、一般に、実装はよりトリッキーで複雑です。

私は個人的にVEBツリーよりもBSTを好むことを考えると、あなたはどう思いますか？

それを簡単に示すことができます：

$ qquad displaystyle forall n <10^6。 frac { log n} { log（ log（n））} <5.26146 $

役に立ちましたか？

解決

$ log n $が$ log（ log n）$よりも速い（$ log（n）$）依然として指数関数的に成長していることを忘れないでください！

実際、$ log（n）$および$ log（ log（n））$の商を見ると、それほど印象的ではありません。

log(n)/log(log(n))
[ソース]

それでも、最大$ 100000ドルのサイズに対して5〜6因子を取得します。より大きなサイズは実際には珍しいことではなく、その要因によるスピードアップは 驚くばかり！それは昼食後に結果を得るか明日だけの結果を得ることとの違いを生むかもしれません。スピードアップの一部は、ツリーの実装のより高い定数に捨てられる可能性があることに注意してください。 $ c cdot log（n）$および$ d cdot log（ log（n））$を$ cでプロット（または分析する）必要があります。

さらに、デイブが言及していることは重要です。操作がこのように実行された場合、たとえば、頻繁に頻繁に、一定のスピードアップが線形スピードアップになる場合、つまり、アルゴリズム全体の主要な定数を減少させる可能性があります。上で言ったように、それは素晴らしいです。 Operation $ n $ timesを実行した場合に何が起こるかを見てください：

n*log(n)/(n*log(log(n)))
[ソース]

今、それがトラブルの価値がないなら、私は何を知りません。

他のヒント

複雑さの違いは実際にはそれほど重要ではなく、実際の実行時間がより重要であると想像できます。しかし、アルゴリズムが別のアルゴリズムの中核にある場合、この違いが重要になる場合があります。

純粋に理論的な目的から、特にアルゴリズムが別のものの一部である場合、もちろんの違いが重要です。大きなアルゴリズムを異なる複雑さクラスに配置する場合があります。

私は実際に一度ヴァン・エムデ・ボースの木をベンチマークしました。 AAツリー、ハッシュマップ、少し配列と比較しました。

テストは実行されます size 間隔に乱数の挿入 [0, bound], 、 それから size 次に、検索 size 削除してからもう一度 size 検索。削除も乱数で行われるため、最初に構造内にあるかどうかを把握する必要があります。

これが結果です（size=2000000, bound= 10000000）秒単位：

AATreeLookup - O(n log n)
Inserting... 3.3652452
Searching... 5.2280724
Deleting...  7.3457427
Searching... 9.1462039
HashLookup - O(n) expected
Inserting... 0.3369505
Searching... 0.6223035
Deleting...  0.9062163
Searching... 1.1718223
VanEmdeBoasTree - O(n log log n)
Inserting... 0.7007531
Searching... 1.1775800
Deleting...  1.7257065
Searching... 2.2147703
ArrayLookup - O(n)
Inserting... 0.0681897
Searching... 0.1720300
Deleting...  0.2387776
Searching... 0.3413800

ご覧のとおり、Van Emde-Boasのツリーは、ハッシュマップの約2倍の低速で、ビットアレイの10倍遅い、バイナリ検索ツリーの5倍の速さです。

もちろん、上記には免責事項が必要です。テストは人工的で、コードを改善したり、出力が速いコンパイラを使用して別の言語を使用したりすることもできます。

この免責事項は、アルゴリズムの設計で漸近分析を使用する理由の中心にあります。定数が何であるかわからないため、環境要因に応じて定数が変化する可能性があるため、私たちができる最善は漸近分析です。

さて、$ log n $ vers $ log log n $の場合、上記の例では、私のvan emde-boasツリーには$ 2^{32} $要素を含めることができます。 $ log 2^{32} = 32 $、および$ log 32 = 5 $、これは因子6の改善であり、実際にはかなりあります。さらに、Van Emde-Boasの木には、バランスをとる必要がないため、van emde-boasの木には一定の要因があります（実際の違いについては、実際には一定の要因がすべてです）。

ライセンス： CC-BY-SA と 帰属
所属していません cs.stackexchange
scroll top