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

Question

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

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

Answer 1

如果你实现 union find algorithm通过路径压缩和按等级并集，并集和查找都将具有复杂性 O(log*(n))。