什么是 O(log* N)?

发布于 2024-08-23 13:48:46 字数 39 浏览 5 评论 0原文

什么是 O(log* N)?它与 O(log N) 有什么不同?

What is O(log* N) and how is it different from O(log N)?

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(3

乖乖兔^ω^ 2024-08-30 13:48:46

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

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

O( log* N ) is "iterated logarithm":

In computer science, the iterated logarithm of n, written log* n (usually read "log star"), is the number of times the logarithm function must be iteratively applied before the result is less than or equal to 1.

弥枳 2024-08-30 13:48:46

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;
}

The log* N bit is an iterated algorithm which grows very slowly, much slower than just log N. You basically just keep iteratively 'logging' the answer until it gets below one (E.g: log(log(log(...log(N)))), and the number of times you had to log() is the answer.

Anyway, this is a five-year old question on Stackoverflow, but no code?(!) Let's fix that - here's implementations for both the recursive and iterative functions (they both give the same result):

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;
}
别把无礼当个性 2024-08-30 13:48:46

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

log* (n)- "log Star n" as known as "Iterated logarithm"

In simple word you can assume log*(n) = log(log(log(.....(log(n))))

log*(n) is very powerful.

Example:

1) Log* (n)=5 where n= Number of atom in universe

2) Tree Coloring using 3 colors can be done in log*(n) while coloring a Tree 2 colors are enough but complexity will be O(n) then.

3) Finding the Delaunay triangulation of a set of points knowing the Euclidean minimum spanning tree: randomized O(n log* n) time.

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文