算法分析中lg * N的含义
我目前正在阅读有关算法分析的内容，并且读到某种算法（带有路径压缩的加权快速联合）的阶数为 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.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
到目前为止，这里给出的答案都是错误的。
lg* n（读作“对数星”）是迭代对数。它被递归地定义为：另一种思考方式是在结果小于或等于 1 之前必须迭代对数的次数。
它的增长速度极其缓慢。您可以在 Wikipedia 上阅读更多内容，其中包括一些
lg* n< 的算法示例/code> 会在分析中弹出。The answers given here so far are wrong.
lg* n(read "log star") is the iterated logarithm. It is defined as recursively asAnother 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.
It grows extremely slowly. You can read more on Wikipedia which includes some examples of algorithms for which
lg* npops up in the analysis.我假设您正在谈论本讲座第 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））。例如，N 值为 2^(2^(65536)) [一个更大的数字] 将给出 lg*N = 6。
I'm assuming you're talking about the algorithm analyzed on slide 44 of this lecture:
http://www.cs.princeton.edu/courses/archive/fall05/cos226/lectures/union-find.pdf
Where they say "lg * N is a constant in this universe" I believe they aren't being entirely literal.
lg*N does appear to increase with N as per their table on the right side of the slide; it just happens to grow at such a slow rate that it can't be considered much else (N = 2^65536 -> log*n = 5). As such it seems they're saying that you can just ignore the log*N as a constant because it will never increase enough to cause a problem.
I could be wrong, though. That's simply how I read it.
edit: it might help to note that for this equation they're defining "lg*N" to be 2^(lg*(N-1)). Meaning that an N value of 2^(2^(65536)) [a far larger number] would give lg*N = 6, for example.
Jason 对 lg*n 的递归定义相当于
lg*n = m 当 2 II m <= n < 2 II (m+1)
哪里
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 接近无穷大的速度极其缓慢。
2 向上箭头的阿克曼函数 A(n,n) 的反函数更快。）
（比涉及 n -
The recursive definition of lg*n by Jason is equivalent to
lg*n = m when 2 II m <= n < 2 II (m+1)
where
2 II m = 2^2^...^2 (repeated exponentiation, m copies of 2)
is Knuth's double up arrow notation. Thus
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.
Hence lg*n=4 for 2^{16} <= n < 2^{65536}.
The function lg*n approaches infinity extremely slowly.
(Faster than an inverse of the Ackermann function A(n,n) which involves n-2 up arrows.)
Stephen
lg 是“LOG”或反指数。 lg 通常指基数 2，但对于算法分析来说，基数通常并不重要。
lg is "LOG" or inverse exponential. lg typically refers to base 2, but for algorithmic analysis, the base usually doesnt matter.
lg n 指以 n 为底的对数。这是方程 2^x = n 的答案。在 Big O 复杂性分析中，日志的基础是无关紧要的。 2 的幂在 CS 中出现，所以如果我们必须选择一个基数，那就是基数 2，这并不奇怪。
它出现的一个很好的例子是高度为 h 的完全二叉树，它有 2^h- 1 个节点。如果我们让 n 为节点数，则该关系是树的高度为 lg n，有 n 个节点。遍历这棵树的算法最多需要 lg n 来查看树中是否存储了一个值。
不出所料，维基百科有很多额外的信息。
lg n refers to log base n. It is the answer to the equation 2^x = n. In Big O complexity analysis, the base to log is irrelevant. Powers of 2 crop up in CS, so it is no surprise if we have to choose a base, it will be base 2.
A good example of where it crops up is a fully binary tree of height h, which has 2^h-1 nodes. If we let n be the number of nodes this relationship is the tree is height lg n with n nodes. The algorithm traversing this tree takes at most lg n to see if a value is stored in the tree.
As to be expected, wiki has great additional info.
对数用log或lg表示。在你的情况下，我猜正确的解释是 N + M * log(N)。
编辑：进行渐近复杂性分析时，对数的底数并不重要。
Logarithm is denoted by log or lg. In your case I guess the correct interpretation is N + M * log(N).
EDIT: The base of the logarithm does not matter when doing asymptotic complexity analysis.