算法分析中lg*N的意义

Question

我正在阅读有关算法分析的内容,我读到某种算法(加权快速联合路径压缩)的顺序为N + M lg*N.显然这是线性的,因为lg*N在这个宇宙中是一个常数.这里提到了什么数学运算.我不熟悉符号lg*N.

Answer 1

到目前为止给出的答案是错误的.lg* n(读"log star")是迭代对数.它被定义为递归的

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

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

它变得非常缓慢.您可以在维基百科上阅读更多内容,其中包括lg* n分析中弹出的算法示例.