“log*”是什么意思?

它是迭代对数。见 here 对于许多不同时间复杂性的描述,以及 here 有关迭代对数本身的更多详细信息。

迭代对数是在结果变为一个或更少之前必须应用对数的次数。

它叫 iterated logarithm function . 这是一个增长非常缓慢的功能。例如:

• lg*(2) = 1
• lg*(4) = 2
• lg*(16) = 3
• lg*(65536) = 4
• lg*(2^65536) = 5 /注意,(2^65536)比可观测宇宙中的原子数大得多。/

或者在大O的情况下,它可以被认为是一个恒定的时间。

对数*(n)-“对数星n”称为“迭代对数”

简单来说,您可以假定log*(n)=log(log(log(…(log*(n)))

对数*(n)非常强大。

例子:

1)对数*(n)=5,其中n=宇宙中的原子数

2)使用3种颜色的树着色可以在日志*(n)中完成,而使用2种颜色的树着色就足够了,但是复杂度将是O(n)。

3)找出已知欧几里得最小生成树的一组点的Delaunay三角剖分:随机O(n log*n)时间。

我希望你能想象 log*(n) 就像沃尔夫拉玛尔帕上的这个 Check here

Log*是在达到小于或等于1的值之前应用Log函数所需的次数。例如:log*(16)=3,因为log _二 (原木) _二 (原木) _二 (16))=1。

出于实际目的,您可以将其视为常量,因为此函数增长非常缓慢。