"log*"是什么意思？

Question

我O(log* N)在一本关于数据结构的书中遇到过这个术语.什么log*意思？我无法在Google上找到它,WolframAlpha 也不理解它.

Answer 1

它被称为迭代对数函数.这是一个非常缓慢增长的功能.例如:

• lg*(2) = 1
• lg*(4) = 2
• lg*(16) = 3
• lg*(65536) = 4
• lg*(2^65536) = 5 /注意(2 ^ 65536)远大于可观察宇宙中的原子数/

或者在Big O的情况下,它几乎可以被认为是恒定的时间.

Answer 2

它是迭代对数.见这里的许多不同的时间复杂度的描述,并在这里对重对数本身的更多细节.

迭代对数是在结果变为1或更小之前必须应用对数的次数.

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

我希望你能在WolframAlpha上像这样可视化Log*(n)这里查看