"日志*"是什么意思？

Question

我曾遇到过一个词 O(log* N) 在我读的一本关于数据结构的书中。 什么是 log* 什么意思？ 我不能 谷歌上找到的和WolframAlpha 也不懂.

Answer 1

就是迭代对数。请看 此处 对于很多不同的时间复杂度的描述，以及。此处 以获得更多关于迭代对数本身的细节。

迭代对数是指在结果变成1或更少之前，必须应用对数的次数。

Answer 2

这就是所谓的 "迭代对数"。迭代对数函数. 这是一个非常缓慢增长的功能。例如：

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

或者在大奥的情况下，几乎可以认为是恒定时间。

Answer 3

log* (n)--"对数星n"，即所谓 "迭代对数"

简单来说，你可以假设log* (n)= log(log(log(......(log* (n))))

log* (n)是非常强大的。

例如

1）对数*（n）=5 其中n=宇宙中的原子数。

2）使用3种颜色的树着色可以在log*(n)中完成，而着色Tree 2种颜色就够了，但复杂度将是O(n)，那么。

3）知道欧几里得最小跨度树后，找到一组点的Delaunay三角关系：随机化O(n log* n)时间。

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

Answer 4

log*是你需要应用对数函数的次数，直到你达到一个小于或等于1的值。例如：log*(16)=3，因为 log₂(对数₂(对数₂(16))) = 1.

出于实际目的，你可以把它当作一个常数，因为这个函数的增长非常缓慢。