在计算机科学中，n的迭代对数，写成log*n（通常读作“对数星”），是在结果小于或等于1之前必须迭代应用对数函数的次数。最简单的正式定义是这个递归函数的结果：
有没有时间复杂度为 O(lg * n) 的算法？
问问题
1139 次
2 回答
4
如果您使用路径压缩和按等级联合来实现联合查找算法O(log*(n))，则联合和查找都将具有复杂性。
于 2015-10-20T10:58:26.233 回答
0
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
并获得二的数字根。每次我们对数字的数字求和时，我们将数字 n 替换为最多为 9 ⌈log10 n⌉ 的数字，因此轮数为 O(log* n)。（话虽这么说，总运行时间是 O(log n)，因为我们必须考虑将数字的数字相加相关的工作，并且将原始数字的数字相加支配运行时间。）
举一个更详细的例子， Goldberg 等人的论文“Parallel Symmetry-Breaking in Sparse Graphs”中描述了一种用于对树的节点进行 3 色着色的并行算法。该算法通过用简单的数字重复替换数字来工作，这些数字是通过对数字的某些位求和而形成的，并且所需的轮数，就像上面提到的方法一样，是 O(log* n)。
希望这可以帮助！
于 2020-04-29T06:47:03.610 回答