algorithm - lg * N在算法分析中的含义

我目前正在阅读有关算法分析的文章，并且我了解到某种算法(带路径压缩的加权快速联合)的阶数为N + M lg *N。显然，这是线性的，因为lg * N在这个宇宙中是一个常数。这里指的是什么数学运算。我不熟悉lg *N。

最佳答案

到目前为止，这里给出的答案是错误的。 lg* n(读取为“log star”)是迭代的​​对数。递归定义为

         0             if n <= 1
lg* n =
         1 + lg*(lg n) if n > 1

另一种思考方式是在结果小于或等于1之前必须对数进行迭代的次数。

它生长非常缓慢。您可以阅读有关Wikipedia的更多信息，其中包括一些在分析中 pop lg* n的算法示例。

关于algorithm - lg * N在算法分析中的含义，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/5212628/