25

O(log* N)私はデータ構造について読んでいる本の中でこの用語に出くわしました。どういうlog*意味ですか？私はそれをグーグルで見つけることができず、WolframAlphaもそれを理解していません。

4

4 に答える 4

27

これは、反復対数関数と呼ばれます。それは非常にゆっくりと成長する機能です。例えば：

  • lg*(2) = 1
  • lg*(4) = 2
  • lg*(16) = 3
  • lg*(65536) = 4
  • lg*(2^65536) = 5/（2 ^ 65536）は、観測可能な宇宙の原子数よりもはるかに大きいことに注意してください/

または、Big Oの場合、それはほぼ一定時間と見なすことができます。

于 2010-09-26T11:46:29.587 に答える
23

反復対数です。多くの異なる時間計算量の説明についてはここを、反復対数自体の詳細についてはここを参照してください。

反復対数は、結果が1以下になる前に対数を適用する必要がある回数です。

于 2010-09-26T11:45:42.990 に答える
5

log *（n）-「反復対数」として知られる「logStarn」

簡単に言えば、log *（n）= log（log（log（.....（log *（n））））と仮定できます。

log *（n）は非常に強力です。

例：

1）Log *（n）= 5ここで、n=宇宙の原子番号

2）3色を使用したツリーのカラーリングはlog *（n）で実行でき、ツリー2のカラーは十分ですが、複雑さはO（n）になります。

3）ユークリッド最小全域木を知っている点のセットのドロネー三角形分割を見つける：ランダム化されたO（n log * n）時間。

WolframAlphaでこのようにログ*（n）を視覚化できることを願っていますここをチェックしてください

于 2014-09-30T06:25:55.857 に答える
2

log *は、1以下の値に達するまでlog関数を適用する必要がある回数です。たとえば、log *（16）= 3であるため、log 2（log 2（log 2（16）） ））=1。

この関数の成長は非常に遅いため、実用的な目的では、定数のように扱うことができます。

于 2017-08-12T14:14:59.347 に答える