What would cause an algorithm to have O(log log n) complexity?

小开

最佳答案

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

平方根收缩

正如在关联问题的答案中提到的，算法具有时间复杂度 O (log n)的一种常见方法是在每次迭代中通过一些常数因子重复减小输入的大小来工作。如果是这种情况，则算法必须在 O (log n)迭代之后终止，因为在用常数进行 O (log n)除法之后，算法必须将问题大小缩小到0或1。这就是为什么二进制搜索具有复杂度 O (logn)的原因。

有趣的是，有一种类似的方法可以缩小问题的大小，从而产生 O 形式的运行时(log log n)。如果我们在每一层都使用 取大小的平方根，会发生什么情况呢？

例如，让我们取数字65,536。我们要把这个除多少次才能得到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，为什么会这样呢？

First, an intuitive explanation. How many digits are there in the numbers n and √n? There are approximately log n digits in the number n, and approximately log (√n) = log (n^1/2) = (1/2) log n digits in √n. This means that, each time you take a square root, you're roughly halving the number of digits in the number. Because you can only halve a quantity k O(log k) times before it drops down to a constant (say, 2), this means you can only take square roots O(log log n) times before you've reduced the number down to some constant (say, 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¹。在每次迭代中，我们将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)步骤之后终止。

现实世界中的一个例子是范 · 埃德 · 博阿斯树(vEB-tree)数据结构。VEB 树是一种特殊的数据结构，用于存储范围为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 最近点对算法。该算法试图在一组2D 点中找到两个最接近的点。它通过创建一个桶网格并将点分布到这些桶中来工作。如果在算法中的任何一个位置发现一个 bucket，其中包含超过√ N 个点，则该算法将递归地处理该 bucket。因此，递归的最大深度是 O (log log n) ，通过对递归树的分析可以看出，树中的每一层都做 O (n)的工作。因此，算法的总运行时间是 O (n log log n)。

小输入下的 O (log n)算法

还有其他一些算法可以通过使用像对大小为 O (logn)的对象进行二进制搜索这样的算法来实现 O (loglogn)运行时。例如，快速尝试数据结构在 at tree of height O (log U)的层上执行二进制搜索，因此其某些操作的运行时为 O (log log U)。相关的快速尝试通过维护每个 O (log U)节点的均衡 BST 来获得一些 O (log log U)运行时，允许在这些树中的搜索在时间 O (log log U)中运行。tango tree和相关的多重播放树数据结构在它们的分析中以 O (log log n)项结束，因为它们维护每个包含 O (log n)项的树。

其他例子

Other algorithms achieve runtime O(log log n) in other ways. 插值搜索 has expected runtime O(log log n) to find a number in a sorted array, but the analysis is fairly involved. Ultimately, the analysis works by showing that the number of iterations is equal to the number k such that n^{2 < sup >-k} ≤ 2, for which log log n is the correct solution. Some algorithms, like the Cheriton-Tarjan MST 算法, arrive at a runtime involving O(log log n) by solving a complex constrained optimization problem.

希望这个能帮上忙！