algorithm - 什么会导致算法具有 O(log log n) 复杂度？

Question

这个较早的问题解决了一些可能导致算法具有 O(log n) 复杂度的因素。

什么会导致算法的时间复杂度为 O(log log n)？

Answer 1

O(log log n) 项可以出现在各种不同的地方，但通常有两条主要路线会在这个运行时到达。

按平方根收缩

如链接问题的答案中所述，算法具有时间复杂度 O(log n) 的常见方法是该算法通过在每次迭代中将输入的大小重复减小某个常数因子来工作。如果是这种情况，算法必须在 O(log n) 次迭代后终止，因为在 O(log n) 除以常数之后，算法必须将问题大小缩小到 0 或 1。这就是为什么，例如，二分查找的复杂度为 O(log n)。

有趣的是，有一种类似的方法可以缩小问题的大小，从而产生 O(log log n) 形式的运行时间。如果我们在每一层取大小的平方根，而不是在每一层将输入分成两半，会发生什么？

例如，让我们以数字 65,536 为例。我们必须将其除以 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

请注意，只需要四个步骤就可以一直到 2。这是为什么呢？

首先，直观的解释。数字 n 和 √n 有多少位数字？数 n 中大约有 log n 位，在 √n 中大约有 log (√n) = log (n ^1/2 ) = (1/2) log n 位。这意味着，每次取平方根时，数字中的位数大致减半。因为你只能将一个数量 k O(log k) 减半，然后它会下降到一个常数（比如 2），这意味着你只能在减少数字之前取平方根 O(log log n) 次到某个常数（例如，2）。

现在，让我们做一些数学来使这个更严谨。让我们用 2 的幂来重写上面的序列：

• √65,536 = √2 ¹⁶ = (2 ¹⁶ ) ^1/2 = 2 ⁸ = 256
• √256 = √2 ⁸ = (2 ⁸ ) ^1/2 = 2 ⁴ = 16
• √16 = √2 ⁴ = (2 ⁴ ) ^1/2 = 2 ² = 4
• √4 = √2 ² = (2 ² ) ^1/2 = 2 ¹ = 2

请注意，我们遵循了 2 ¹⁶ → 2 ⁸ → 2 ⁴ → 2 ² → 2 ¹的顺序。在每次迭代中，我们将二的幂的指数减半。这很有趣，因为这与我们已经知道的有关——你只能将数字 k 除以 O(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)。因此，如果有算法通过重复将问题缩减为大小为原始问题大小的平方根的子问题来工作，则该算法将在 O(log log n) 步后终止。

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

另一个例子是Hopcroft-Fortune 最接近点对算法。该算法试图在二维点集合中找到两个最近的点。它通过创建一个桶网格并将点分布到这些桶中来工作。如果在算法中的任何点发现一个桶中包含超过 √N 个点，则该算法递归地处理该桶。因此，递归的最大深度是 O(log log n)，并且使用对递归树的分析可以证明树中的每一层都做了 O(n) 的工作。因此，算法的总运行时间为 O(n log log n)。

O(log n) 小输入的算法

还有一些其他算法通过对大小为 O(log n) 的对象使用二进制搜索等算法来实现 O(log log n) 运行时。例如，x-fast trie数据结构在高度为 O(log U) 的 at 树的层上执行二进制搜索，因此其某些操作的运行时间为 O(log log U)。相关的y-fast trie通过维护每个 O(log U) 节点的平衡 BST 来获得一些 O(log log U) 运行时，从而允许在这些树中的搜索在 O(log log U) 时间内运行。探戈树和相关的多重播放树数据结构在他们的分析中以 O(log log n) 项结束，因为它们维护的树每个都包含 O(log n) 个项目。

其他例子

其他算法以其他方式实现运行时 O(log log n)。 插值搜索预计运行时 O(log log n) 会在排序数组中找到一个数字，但分析相当复杂。最终，分析表明迭代次数等于数 k 使得 n ^{2 -k} ≤ 2，其中 log log n 是正确的解决方案。一些算法，如Cheriton-Tarjan MST 算法，通过解决复杂的约束优化问题达到了涉及 O(log log n) 的运行时。

希望这可以帮助！

Answer 2

在时间复杂度中查看 O(log log n) 因子的一种方法是通过除法，就像另一个答案中解释的那样，但是当我们想要在时间和空间/时间之间进行交易时，还有另一种方法可以看到这个因子和算法的近似/时间和硬度/...，我们对我们的算法进行了一些人工迭代。

例如 SSSP（单源最短路径）在平面图上有一个 O(n) 算法，但在那个复杂的算法之前有一个更简单的算法（但仍然相当困难），运行时间为 O(n log log n)，算法的基础如下（只是非常粗略的描述，我建议跳过理解这部分并阅读答案的另一部分）：

1. 将图分成大小为 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) 中完成。有关更多详细信息，此讲义很好。

但我的意思是，这里我们选择大小为 O(log n/(log log n)) 的除法。如果我们选择像 O(log n/ (log log n)^2) 这样的其他划分，它可能会运行得更快并带来另一个结果。我的意思是，在很多情况下（比如在近似算法或随机算法中，或者像上面的 SSSP 算法），当我们迭代某些东西（子问题，可能的解决方案，......）时，我们选择与该交易相对应的迭代次数我们有（时间/空间/算法的复杂性/算法的常数因子，...）。所以我们可能会在实际工作算法中看到比“log log n”更复杂的东西。