lg*N在算法分析中的意义。

Question

我目前在看算法分析，我看到某算法（加权快速联合与路径压缩）的阶数是N+M lg * N，显然虽然这是线性的，因为lg * N是这个宇宙中的一个常数。这里指的是什么数学运算。我对lg * N这个符号不熟悉。

Answer 1

目前这里给出的答案都是错误的。lg* n 读作 "对数星"）是迭代对数。它的递归定义为

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

另一种想法是，在结果小于或等于1之前，你必须迭代对数的次数。

它的增长速度极慢。你可以阅读更多关于 维基百科 其中包括一些算法的例子，其中 lg* n 在分析中弹出。

Answer 2

我猜你说的是本讲座第44张幻灯片上分析的算法。http: /www.cs.princeton.educoursesarchivefall05cos226lecturesunion-find.pdf

他们说 "lg*N是这个宇宙中的一个常数"，我相信他们并不是完全按照字面意思来理解的。lg*N确实会随着N的增加而增加，根据他们在幻灯片右侧的表格，它只是碰巧以如此缓慢的速度增长，以至于它不能被认为是别的什么（N=2^65536 -&gt；log*n=5）。因此，他们似乎在说，你可以忽略log*n这个常数，因为它永远不会增加到足以引起问题。

不过，我可能是错的。这只是我的理解。

edit: 可能有助于注意到，对于这个公式，他们定义 "lg*N "为2^(lg*(N-1))。意思是N值为2^(2^(65536)) 例如，[一个大得多的数字]将给出lg*N=6。

Answer 3

递推的定义是： lg*n 由杰森相当于lg*n = m 当 2 II m <=n < 2 II (m+1)哪儿 2 II m = 2^2^...^2 (重复指数化。m 2）的副本是Knuth的双上箭头符号。因此 lg*2=1，lg*2^2=2，lg*2^{2^2}=3，lg*2^{2^{2^2}}=4，lg*2^{2^{2^2}}=5。 因此 lg*n=4 对于 2^{16} <=n < 2^{65536}。.该功能 lg*n 比阿克曼函数的倒数还慢。A(n,n) 其中涉及 n-2 上箭头。)

斯蒂芬

Answer 4

lg是 "LOG "或反指数。lg通常指的是基数2，但对于算法分析，基数通常并不重要。

Answer 5

lg n指的是对数基数n，它是方程2^x=n的答案。在大O复杂性分析中，基数与对数无关。2的幂级数在CS中出现，所以如果我们必须选择一个基数，它将是基数2也就不足为奇了。

一个很好的例子是高度为h的全二进制树，它有2^h-1个节点。如果我们让n是节点数，这个关系是树的高度lg n，有n个节点。遍历这棵树的算法最多需要lg n的时间来查看树中是否存储了一个值。

正如预期的那样，wiki有很多额外的信息。

Answer 6

对数 在你的情况下，我猜正确的解释是N + M * log(N)。

编辑：在做渐近复杂性分析时，对数的基数并不重要。