algorithm - O（log * N）とは何ですか？

Question

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

Answer 1

O( log* N )「反復対数」です：

コンピュータサイエンスでは、nの反復対数（log * n（通常は「ログスター」と読みます））は、結果が1以下になる前に対数関数を繰り返し適用する必要がある回数です。

Answer 2

log* Nビットは非常にゆっくりと成長する反復アルゴリズムであり、単にlog N. 基本的には、答えが1未満になるまで繰り返し「ログに記録」し続けます（例：log(log(log(...log(N)))）。必要な回数がlog()答えです。

とにかく、これは Stackoverflow に関する 5 年前の質問ですが、コードはありませんか?(!) 修正しましょう - 再帰関数と反復関数の両方の実装を次に示します (どちらも同じ結果が得られます)。

public double iteratedLogRecursive(double n, double b)
{
    if (n > 1.0) {
        return 1.0 + iteratedLogRecursive( Math.Log(n, b),b );
    }
    else return 0;
}

public int iteratedLogIterative(double n, double b)
{
    int count=0;
    while (n >= 1) {
        n = Math.Log(n,b);
        count++;
    }
    return count;
}

Answer 3

log* (n) - 「反復対数」として知られる「log Star n 」

簡単に言えば、 log* (n)= log(log(log(.....(log* (n)))) と仮定できます

log* (n) は非常に強力です。

例：

1) Log* (n)=5 ここで、n= 宇宙の原子の数

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

3)ユークリッド最小スパニング ツリーを知っている一連のポイントの Delaunay 三角形分割を見つける: ランダム化された O(n log* n) 時間。