什么是 O(log* N)？

Question

什么是 O(log* N) 以及它与 O(log N) 有什么不同？

Answer 1

O( log* N )

是“迭代对数”：

在计算机科学中，n 的迭代对数，写作 log* n（通常读作“log star”），是在结果小于或等于 1 之前必须迭代应用对数函数的次数。

Answer 2

log* N

位是一种迭代算法，其增长非常缓慢，比

log N

慢得多。您基本上只是不断迭代地“记录”答案，直到它低于 1（例如：

log(log(log(...log(N)))

），而您必须

log()

的次数就是答案。

无论如何，这是 Stackoverflow 上五年前的问题，但没有代码？（！）让我们解决这个问题 - 这里是递归函数和迭代函数的实现（它们都给出相同的结果）：

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) 时间。