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

Question

在计算机科学中，迭代对数（iterated logarithm）是一个与对数函数相关的概念，通常用log* n表示，表示对数函数必须递归地应用多少次才能使结果小于或等于1。最简单的形式定义是这个递归函数的结果：

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

- Naveen N

---

检查已排序的值数组是否包含给定值可以在O(log n)时间内完成。它可以使用递归或迭代算法来完成。 - Luca Angeletti

@appzYourLife，这是O(log n)而不是O(log* n)。 - aioobe

https://en.wikipedia.org/wiki/Iterated_logarithm#Analysis_of_algorithms - cohoz

考虑到任何增长速度更慢的东西也属于这个类别，例如O(1)包含在O(log* n)中。 - harold

@harold是正确的。你应该要求一个运行在theta(log*n)时间复杂度的算法。 - dsharew

Answer 1

如果使用路径压缩和按秩合并的 并查集算法，则合并和查找操作的时间复杂度均为O(log*(n))。

- Ivaylo Strandjev

---

尽管如此，这并不是一个紧密的界限。更好的边界是O(alpha(m, n)), 其中alpha(m, n)是m和n的阿克曼逆函数。 - templatetypedef

在这种情况下，m 是什么？ - Ivaylo Strandjev

通常，分析需要处理m个操作和n个节点。 - templatetypedef

Answer 2

在算法的运行时间分析中看到log * n出现是罕见但并非闻所未闻的。以下是一些常见情况，可能导致出现log * n。

方法1：通过对数因子缩小

许多分治算法通过将大小为n的输入转换为大小为n / k的输入来工作。这些算法的阶段数为O(log n)，因为您只能将其除以常数O(log n)次，然后将输入缩小到恒定大小。从这个意义上说，当您看到“输入被除以一个常数”时，您应该想“因此我们只能将其除以O(log n)次，然后就没有东西可以继续除了。”

在更罕见的情况下，一些算法通过对输入进行对数因子的缩小来工作。例如，一种用于范围半群查询问题的数据结构通过将一个较大的问题分解成大小为log n的块，然后递归地将每个大小为log n的块细分为大小为log log n的块等来工作。这个过程最终会在块达到某个小常数大小时停止，这意味着它在O(log* n)次迭代后停止。（这种特定的方法可以进一步改进，以给出一个数据结构，其中块的大小为log* n，总轮数为O(log** n)，最终收敛到具有运行时间O(α(n))的最优结构，其中α(n)是反阿克曼函数。

方法2：压缩数字

上面的部分讨论了一种将一个较大的问题明确地分解成较小的多个部分的方法，这些部分的大小与原始问题的大小的对数成比例。然而，还有另一种将大小为n的输入减小到大小为O(log n)的输入的方法：用与其位数大致相当的东西替代输入。由于写出数字n需要O(log n)位数，因此这样做会将数字的大小缩小到产生一个O(log* n)项所需的程度。

举个简单的例子来说明，考虑一个计算数字根的算法。数字根是指将一个数字的各位数相加，直到得到一个个位数为止。例如，数字78979871的数字根可以通过以下计算得到：

7 + 8 + 9 + 7 + 9 + 8 + 7 + 1 = 56

5 + 6 = 11

1 + 1 = 2

2

并获得数字根为二。每次我们将数字的各个位数相加，用不超过9⌈log10 n⌉的数字替换数字n，因此循环次数为O(log* n)（话虽如此，总运行时间为O(log n)，因为我们必须考虑加上数字的位数所需的工作，并且添加原始数字的位数支配了运行时间。）

更详细的例子是，在Goldberg等人的论文{{link1：“Parallel Symmetry-Breaking in Sparse Graphs”}}中描述了一种用于给树的节点上色的并行算法。该算法通过反复替换数字为通过对数字的某些位求和形成的更简单的数字进行处理，像上面提到的方法一样，所需的循环轮数为O(log* n)。

希望这可以帮助你！

- templatetypedef