algorithm - 什么是 O(log* N)？

Question

什么是 O(log* N)，它与 ​​O(log N) 有何不同？

Answer 1

O( log* N )是“迭代对数”：

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

Answer 2

bit 是一种迭代算法，它的log* N增长非常缓慢，比log N. 您基本上只是反复“记录”答案，直到它低于一个（例如：）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）时间。