问题标签 [iterated-logarithm]

什么是 O(log* N)，它与 ​​O(log N) 有何不同？

我在正在阅读的有关数据结构的书中遇到了这个术语O(log* N)。是什么log*意思？我在 Google 上找不到它，WolframAlpha也不明白。

我目前正在阅读有关算法分析的内容，并且我读到某个算法（带有路径压缩的加权快速联合）的顺序为 N + M lg * N。显然这是线性的，因为 lg * N 在这个宇宙中是一个常数。这里指的是什么数学运算。我不熟悉符号 lg * N。

随着 n 变大，两个函数 log*(log n) 和 log(log* n) 会更快吗？

这里，log* 函数是迭代的对数，在这里定义：

我怀疑这些是相同的，只是写法不同，但是它们之间有什么区别吗？

假设迭代对数的定义如下：http ://en.wikipedia.org/wiki/Iterated_logarithm

例如，我应该如何将其复杂性与其他功能进行比较lg(lg(n))？到目前为止，我已经通过计算限制完成了所有比较，但是如何计算迭代对数的限制？

我知道它的增长非常缓慢，比 慢lg(n)，但是是否有一些函数的增长速度可能与lg*(n)（lg*基数为 2 的迭代对数在哪里）相同，因此它可以轻松地将其与其他函数进行比较？这样我也可以比较lg*(lg(n))例如lg(lg*(n))。任何关于根据增长速度相互比较功能的技巧将不胜感激。

在计算机科学中，n的迭代对数，写成log*n（通常读作“对数星”），是在结果小于或等于1之前必须迭代应用对数函数的次数。最简单的正式定义是这个递归函数的结果：

有没有时间复杂度为 O(lg * n) 的算法？

Log * 是 log 必须应用于 value 直到它小于或等于 1 的次数。

根据我对序言中递归工作方式的理解，当我到达 N<1 的基本情况时，应该返回 A，并且在堆栈的下一级，Arev 应该被推断为 A +1 或 Aprev 是 1 等等直到它到达返回 A 的堆栈顶部。

当我遇到 N<1 的情况时，我尝试将 0 返回到堆栈上的前一层，而不是得到一个参数没有充分实例化的错误。

我正在学习联合/查找结构的“带路径压缩的加权快速联合”算法。普林斯顿教育网站详细解释了该算法。这是Java中的实现：

但就像网站提到它的性能一样：

定理：从一个空数据结构开始，对 N 个对象的任何 M 个 union 和 find 操作序列都需要 O(N + M lg* N) 时间。

• 证明非常困难。

• 但算法仍然很简单！

但是我还是很好奇迭代对数lg*n是怎么来的。它是如何派生的？有人可以证明它还是以直观的方式解释它？

我有两个疑问：-

1) 是 (log* n)^n = O((logn)!) 吗？

2) log(log* n) 或 log*(logn) 哪个更大？

我有两个数学函数：log(log*n) 和2^(log*n)。现在，我想计算这两个函数的渐近增长（特别是我想找到大 theta）。最后，我想比较一下它们的复杂性。谁能分享一个可以解决此类问题的正式/直观的解决方案？

谢谢。