問題タブ [iterated-logarithm]

O（log * N）とは何ですか？O（log N）とはどう違うのですか？

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

私は現在アルゴリズム分析について読んでおり、特定のアルゴリズム（パス圧縮を使用した加重クイックユニオン）はN + M lg * Nのオーダーであると読みました。これは線形ですが、lg*Nはこのユニバースでは定数であるためです。ここでは、どのような数学演算が参照されていますか。lg*Nという表記に慣れていません。

n が大きくなると、log*(log n) と log(log* n) の 2 つの関数のほうが速くなりますか?

ここで、log* 関数は反復対数であり、次のように定義されています。

書き方が違うだけで同じだと思いますが、違いはありますか？

Log * は、値が 1 以下になるまでログを値に適用する必要がある回数です。

N<1 の基本ケースに到達したときにプロローグで再帰が機能する方法についての私の理解から、A を返す必要があり、スタックの次のレベルでは、Aprev は A +1 または Aprev が 1 であると推測される必要があります。 A が返されるスタックの一番上に到達するまでオンになります。

N<1 の場合に到達すると、スタックの前のレイヤーに 0 を返そうとする代わりに、引数が十分にインスタンス化されていないというエラーが発生します。

ユニオン/検索構造の「パス圧縮による加重クイックユニオン」アルゴリズムを学習しています。Princeton edu サイトでは、アルゴリズムについて詳しく説明されています。Java での実装は次のとおりです。

しかし、ウェブサイトがそのパフォーマンスについて言及しているように：

定理: 空のデータ構造から開始すると、N 個のオブジェクトに対する M 個の和集合と検索操作のシーケンスは、O(N + M lg* N) 時間かかります。

• 証明は非常に難しい。

• しかし、アルゴリズムは依然として単純です。

しかし、反復対数 lg*n がどのように得られるかについてはまだ興味があります。それはどのように導出されますか？誰かがそれを証明したり、直感的に説明したりできますか?

私は2つの疑問があります:-

1) (log* n)^n = O((logn)!) ですか?

2) log(log* n) と log*(logn) のどちらが大きいですか?