有没有时间复杂度为 O(lg * n) （迭代对数函数）的算法？

Question

在计算机科学中，n的迭代对数，写成log*n（通常读作“log star”），是对数函数在结果小于或等于1之前必须迭代应用的次数。 最简单的形式定义是这个递归函数的结果：

有没有时间复杂度为 O(lg * n) 的算法？

Answer 1

如果您使用路径压缩和按等级并集来实现并集查找算法O(log*(n))，则并集和查找都会具有复杂性。