algorithm - O(m log(log* n)) 和具有迭代日志函数的 O(m log* n) 之间的区别

Question

当我在算法课上谈论最小生成树时，我的教授介绍了 Fredman 和 Tarjan 从 O(m log* n) 到 O(m log(log* n)) 的性能增强。

我对迭代日志的记录感到非常困惑。看起来 log* n 本质上是取无限多的日志，所以对我来说这就像将无穷大与无穷大 +1 进行比较。

谁能给个解释？也欢迎类比。

---

更新:

感谢您快速回答并纠正我!

进一步的问题:

似乎这种复杂性来自于迭代算法。

如果我们可以把迭代日志多取一个log，为什么不能多取一个得到O(m log(log(log* n)))来进一步降低复杂度呢？

---

谢谢 amit !

我需要改进概念哈哈!

Answer 1

log*是为了使该值无效而需要获取 log 的次数。

这不是无限时间日志。取无穷大的时间日志，最后只会是负数，然后就是undefined，这里没有意义。

例如:

log*(2^1024) = 1 + log*(log(2^1024)) = 1 + log*(1024) = 1 + 1 + log*(log(1024) = 2 + log*(10)
             = 2 + 1 + log*(log(10)) = 3 + log*(3) = 3 + 1 + log*(log(3)) = 4 + log*(2)
             = 4 + 1 + log*(log(2)) = 5 + log*(1) = 5

另一方面，现在

 log(log*(2^1024)) = log(5) = 3

(上面所有的log都是以2为底，我一直取非整数的ceil值，这些假设不改变这里解释的原理)

UPDATE(对相关更新的响应):

您不能只创建一个额外的日志，因为您需要对实现它的算法进行额外的改进。

你从 O(m log*(n)) 到 O(m log(log*(n)) 的改进不是凭空而来的，它来了来自对算法的一些改进。如果你能找到具有类似行为的另一个改进，你可能能够得到 O(m log(log(log*(n))))。