什么是 O(log* N)?
什么是 O(log* N)?它与 O(log N) 有什么不同?
What is O(log* N) and how is it different from O(log N)?
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
什么是 O(log* N)?它与 O(log N) 有什么不同?
What is O(log* N) and how is it different from O(log N)?
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
接受
或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
发布评论
评论(3)
O( log* N )
是“迭代对数”:O( log* N )
is "iterated logarithm":log* N
位是一种迭代算法,其增长非常缓慢,比log N
慢得多。基本上,您只需不断迭代“记录”答案,直到其低于 1(例如:log(log(log(...log(N)))
),以及您必须记录的次数log()
就是答案。无论如何,这是 Stackoverflow 上一个五年前的问题,但没有代码?(!)让我们解决这个问题 - 这里是递归函数和迭代函数的实现(它们都是)给出相同的结果):
The
log* N
bit is an iterated algorithm which grows very slowly, much slower than justlog N
. You basically just keep iteratively 'logging' the answer until it gets below one (E.g:log(log(log(...log(N)))
), and the number of times you had tolog()
is the answer.Anyway, this is a five-year old question on Stackoverflow, but no code?(!) Let's fix that - here's implementations for both the recursive and iterative functions (they both give the same result):
log* (n)- “log Star n” 称为“迭代对数”
简而言之,您可以假设 log*(n) = log(log(log( .....(log(n))))
log*(n) 非常强大
示例:
1) Log* (n)=5 其中 n=宇宙中的原子数量
2) 使用 3 种颜色的树着色可以在 log*(n) 中完成,而为树着色 2 种颜色就足够了,但复杂度将是 O(n)。
3) 查找已知欧几里得最小生成树的一组点的 Delaunay 三角剖分:随机化 O(n log* n) 时间。
log* (n)- "log Star n" as known as "Iterated logarithm"
In simple word you can assume log*(n) = log(log(log(.....(log(n))))
log*(n) is very powerful.
Example:
1) Log* (n)=5 where n= Number of atom in universe
2) Tree Coloring using 3 colors can be done in log*(n) while coloring a Tree 2 colors are enough but complexity will be O(n) then.
3) Finding the Delaunay triangulation of a set of points knowing the Euclidean minimum spanning tree: randomized O(n log* n) time.