什么会导致algorithm有O（log log n）的复杂性？

这个较早的问题解决了一些可能导致algorithm具有O（log n）复杂度的因素。

什么会导致一个algorithm的时间复杂度O（log log n）？

Answer 1

O（日志日志）条款可以在各种不同的地方显示出来，但通常有两条主要路线将到达此运行时间。

用平方根收缩

正如在链接问题的答案中所提到的，algorithm具有时间复杂度O（log n）的一种常见方式是通过在每次迭代中将input的大小重复下降一定的因子来工作。 如果是这种情况，algorithm必须在O（log n）迭代之后终止，因为在执行O（log n）除以常量之后，algorithm必须将问题的大小缩小到0或1.这就是为什么，二分查找具有复杂度O（log n）。

有趣的是，还有一种类似的方式来缩小产生O（log log n）forms的运行时间的问题的大小。 如果我们在每一层取大小的平方根，会发生什么情况？

例如，我们以65,536的数字。 我们有多less次必须除以2，直到我们降到1？ 如果我们这样做，我们得到

• 65,536 / 2 = 32,768
• 32,768 / 2 = 16,384
• 16,384 / 2 = 8,192
• 8,192 / 2 = 4,096
• 4,096 / 2 = 2,048
• 2,048 / 2 = 1,024
• 1,024 / 2 = 512
• 512/2 = 256
• 256/2 = 128
• 128/2 = 64
• 64/2 = 32
• 32/2 = 16
• 16/2 = 8
• 8/2 = 4
• 4/2 = 2
• 2/2 = 1

这个过程需要16个步骤，65,536 = 2 ¹⁶也是这样。

但是，如果我们在每个层面上取平方根，我们就可以得到

• √65,536= 256
• √256= 16
• √16= 4
• √4= 2

请注意，只需要四步即可完成。为什么会这样呢？ 那么，让我们用两个幂来重写这个序列：

• √65,536=√216 =（2 ¹⁶ ） ^1/2 = 2 ⁸ = 256
• √256=√28 =（2 ⁸ ） ^1/2 = 2 ⁴ = 16
• √16=√24 =（2 ⁴ ） ^1/2 = 2 ² = 4
• √4=√22 =（2 ² ） ^1/2 = 2 ¹ = 2

请注意，我们遵循序列2 ¹⁶ →2 ⁸ →2 ⁴ →2 ² →2 ¹ 。 在每次迭代中，我们将二的幂的指数减半。 这很有意思，因为这跟我们已经知道的有关 – 你只能把数字k分成两半（log k）次，然后再降到零。

因此，取任意数字n并写为n = 2 ^k 。 每次你取n的平方根，就把这个方程中的指数减半。 因此，在k降到1或更低之前（在这种情况下n降到2或更低）之前，只能应用O（log k）平方根。 由于n = 2 ^k ，这意味着k = log ₂ n，因此取平方根的个数为O（log k）= O（log log n）。 因此，如果存在通过将问题重复地减less到原始问题尺寸的平方根的子问题的algorithm，则该algorithm将在O（log log n）步骤之后终止。

一个真实的例子是van Emde Boas树 （vEB-tree）数据结构。 vEB-tree是一个专门的数据结构，用于存储0 … N-1范围内的整数。它的工作原理如下：树的根节点具有√N个指针，分割范围0 … N – 1转换成√N桶，每个桶都有一个大约为√N的整数范围。 这些桶然后在内部被细分为√（√N）桶，其中每个桶大约包含√（√N）个元素。 为了遍历树，你从根开始，确定你属于哪个桶，然后在适当的子树中recursion地继续。 由于vEB树的结构化方式，你可以在O（1）时间内确定哪个子树要下降，所以在O（log log N）之后，你将到达树的底部。 因此，在vEB-tree中查找只需要O（log log N）时间。

另一个例子是Hopcroft-Fortune最接近的一对点algorithm 。 该algorithm试图find2D点集合中的两个最近点。 它通过创build一个桶的网格并将点分布到这些桶中来工作。 如果在algorithm的任何一点发现一个桶中有超过√N的点，则该algorithmrecursion地处理该桶。 因此，recursion的最大深度是O（log log n），并且使用recursion树的分析可以显示树中的每个层都是O（n）。 因此，该algorithm的总运行时间是O（n log log n）。

O（log n）小型inputalgorithm

还有一些其他algorithm可以通过在大小为O（log n）的对象上使用二进制search等algorithm来实现O（log log n）运行时。 例如， x-fast trie数据结构在高度为O（log U）的树的层上执行二进制search，因此其运行时的某些操作是O（log log U）。 相关的y-fast trie通过维护每个O（log U）节点的平衡BST来获得它的一些O（log_log_U）运行时间，允许那些树中的search在时间O（log_log_U）中运行。 探戈树和相关的多显示树数据结构在他们的分析中最终有一个O（log log n）项，因为它们维护包含O（log n）项的树。

其他例子

其他algorithm以其他方式实现运行时O（log log n）。 插值search期望运行时O（log log n）在sorting数组中find一个数字，但是分析是相当复杂的。 最终，分析工作表明，迭代的次数等于数k，使得n ^{2 -k≤2} ，对数log n是正确的解。 一些algorithm，如Cheriton-Tarjan MSTalgorithm ，通过解决一个复杂的约束优化问题来达到涉及O（log log n）的运行时间。

希望这可以帮助！

Answer 2

在时间复杂度中看到O（log log n）的因素的一种方法是通过在另一个答案中解释的东西来进行划分，但是还有另一种方法来看待这个因素，当我们想要在时间和空间/时间之间进行交易时和近似/时间和硬度/ …algorithm，我们有一些人工迭代我们的algorithm。

例如SSSP（单源最短path）在平面图上有一个O（n）algorithm，但是在这个复杂的algorithm之前，运行时间O（n log log n）有一个更简单的algorithm（但仍然相当困难），algorithm的基础如下（只是非常粗略的描述，我会提供跳过理解这部分，并阅读答案的其他部分）：

1. 将graphics划分为O（log n /（log log n））部分，并加以限制。
2. 假设每个提到的部分都是新图G'中的节点，那么在时间O（| G'| * log | G'|）==>中计算G'的SSSP，因为| G'| = O（| G | * log log n / log n）我们可以看到（log log n）因子。
3. 为每个部分计算SSSP：再次因为我们有O（| G'|）部分，我们可以及时计算所有部分的SSSP | n / logn | * | log n / log logn * log（logn / log log n）。
4. 更新权重，这部分可以在O（n）中完成。 更多细节， 这个讲座很好。

但是我的观点是，在这里我们select大小为O的分区（log n /（log log n））。 如果我们selectO（log n /（log log n）^ 2）等其他的分区，可能会运行得更快，并带来另一个结果。 我的意思是，在许多情况下（如近似algorithm或随机algorithm，或像上面的SSSPalgorithm），当我们迭代某些东西（子问题，可能的解决scheme，…）时，我们select对应于我们有（algorithm的时间/空间/algorithm/常数因子的复杂度，…）。 所以在实际的工作algorithm中，我们可能会看到比“log log n”更复杂的东西。