lg * N在算法分析中的含义 [英] Meaning of lg * N in Algorithmic Analysis

问题描述

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

I'm currently reading about algorithmic analysis and I read that a certain algorithm (weighted quick union with path compression) is of order N + M lg * N. Apparently though this is linear because lg * N is a constant in this universe. What mathematical operation is being referred to here. I am unfamiliar with the notation lg * N.

推荐答案

到目前为止，此处给出的答案是错误的。 lg * n （读为 log star）是迭代对数。递归定义为

The answers given here so far are wrong. lg* n (read "log star") is the iterated logarithm. It is defined as recursively as

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

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

Another way to think of it is the number of times that you have to iterate logarithm before the result is less than or equal to 1.

它的增长非常缓慢。您可以在维基百科上阅读更多内容，其中包括 lg的一些算法示例* n 会弹出分析。

It grows extremely slowly. You can read more on Wikipedia which includes some examples of algorithms for which lg* n pops up in the analysis.

这篇关于lg * N在算法分析中的含义的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！