25

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

4

6 回答 6

38

到目前为止，这里给出的答案是错误的。lg* n（阅读“对数星”）是迭代对数。它被定义为递归地

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

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

它生长极其缓慢。您可以在Wikipedia上阅读更多内容，其中包括lg* n分析中弹出的一些算法示例。

于 2011-03-06T19:10:09.087 回答
0

我假设您正在谈论本讲座幻灯片 44 中分析的算法： http ://www.cs.princeton.edu/courses/archive/fall05/cos226/lectures/union-find.pdf

在他们说“lg * N 是这个宇宙中的常数”的地方，我相信他们并不完全是字面意思。根据幻灯片右侧的表格，lg*N 确实随着 N 的增加而增加；它恰好以如此缓慢的速度增长，以至于不能考虑太多其他因素（N = 2^65536 -> log*n = 5）。因此，他们似乎在说您可以忽略 log*N 作为常数，因为它永远不会增加到足以引起问题。

不过，我可能是错的。我就是这么读的。

编辑：请注意，对于这个等式，他们将“lg*N”定义为 2^(lg*(N-1))。例如，这意味着 2^(2^(65536)) [一个更大的数字] 的 N 值将给出 lg*N = 6。

于 2011-03-06T19:01:29.853 回答
0

Jason 对lg*n的递归定义等价于lg*n = m when 2 II m <= n < 2 II (m+1) where
2 II m = 2^2^...^2（重复取幂， 2) 的m个副本
是 Knuth 的双向上箭头符号。因此
lg*2= 1, lg*2^2= 2, lg*2^{2^2}= 3, lg*2^{2^{2^2}} = 4, lg*2^{2^ {2^{2^2}}} = 5。
因此lg*n=4对于2^{16} <= n < 2^{65536}。函数lg*n非常缓慢地接近无穷大。（比涉及n-2 个向上箭头的阿克曼函数A(n,n)的逆函数更快。）

斯蒂芬

于 2013-04-24T06:03:34.727 回答
-4

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

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

正如所料，wiki 有很多额外的信息。

于 2011-03-06T19:00:49.180 回答
-4

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

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

于 2011-03-06T18:55:31.537 回答
-4

lg 是“LOG”或反指数。lg 通常指的是基数 2，但对于算法分析，基数通常无关紧要。

于 2011-03-06T18:56:03.623 回答