什么是O(log*N)？

Question

什么是O(log* N)？

我知道大哦,这log*是未知的.

Answer 1

O( log* N )是" 迭代对数 ":

在计算机科学中,n的迭代对数,写入log*n(通常为"log star"),是在结果小于或等于1之前必须迭代地应用对数函数的次数.

Answer 2

该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)时间.