是否存在时间复杂度为O（lg * n）（迭代对数函数）的算法？

Question

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

是否存在时间复杂度为O（lg * n）的算法？

Answer 1

如果使用路径压缩和按等级联合实现union find algorithm，则联合和查找都将具有复杂性O(log*(n))。

Answer 2

在算法的运行时分析中很少会看到log * n出现，但并非闻所未闻。这是几种可能导致log * n出现的情况。