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

Question

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

algorithmbig-otime-complexitycomplexity-theorylogarithm

123

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

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

- templatetypedef

3个回答

3

在时间复杂度中看到O(log log n)因子的一种方法是通过类似于其他答案中解释的除法，但是还有另一种方法可以看到这个因子，当我们想要在算法的时间和空间/时间和逼近/时间和难度等方面进行权衡，并且我们的算法上有一些人为的迭代时。

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

将图分成大小为 O(log n/(log log n)) 的部分，但有一些限制。
假设提到的每个部分是新图 G' 中的节点，然后在时间 O(|G'|*log |G'|) 内计算 G' 的 SSSP ==> 这里因为 |G'| = O(|G|*log log n/log n)，我们可以看到 (log log n) 因子。
计算每个部分的 SSSP：同样因为我们有 O(|G'|) 部分，并且我们可以在时间 |n/logn| * |log n/log logn * log (logn /log log n) 内计算所有部分的 SSSP。
更新权重，这部分可以在 O(n) 内完成。有关更多详细信息，请参见 this lecture notes。

但我的观点是，这里我们选择的分割大小为O(log n/(log log n))。如果我们选择其他分割，如O(log n/(log log n)^2)，可能会更快地运行并带来另一个结果。我的意思是，在许多情况下（例如近似算法、随机化算法或像上面的SSSP算法），当我们迭代某些东西（子问题、可能的解决方案等）时，我们选择与我们拥有的交易相对应的迭代次数（时间/空间/算法复杂度/算法的常数因子等）。因此，在真正的工作算法中，我们可能会看到比“log log n”更复杂的东西。

- Saeed Amiri

0

@templatetypedef的最高评分答案在很大程度上是正确的，但也有一些注意事项。

更精确的答案应该是“任何算法，每次迭代都将熵的位数减少一个恒定（成比例）的因子”。并不一定需要子集的大小是平方根大小（将熵的位数减半），尽管在某些算法中是这样的。

插值搜索的完整分析可能有些复杂，正如答案所指出的，但总结的解释非常直观。

在一个排序的N个整数随机分布在某个区间上的列表中，插值误差（定义为期望平均值与实际大于或小于某个给定数字的键数之间的差异）可以被证明是以期望平均值为中心的高斯分布，标准差与O(N^1/2)成比例。

换句话说，我们有很高的概率在离真实索引O(N^1/2)的距离范围内找到。在第二次之后，递归地应用这个分析O(N^1/4)。

我们可以从递归中找到渐近时间： T(N) = T(N^1/2) + O(1)

如果我们设置N=2^n： T(2^n) = T(2^(n/2)) + O(1)

重新定义递归，以n为基础，其中T'(n) = T(2^n)。 T'(n) = T'(n/2) + O(1)

使用主定理，我们得到： T'(n) = O(log n)

但是由于n = log N，我们得到： T(N) = O(log log N)

请注意，这种分析中的1/2（或平方根）因子并没有什么特殊之处，对于任何小于1的常数因子a，都会得到相同的结果。

例如，有些尝试中，位递归被分为搜索的上半部分和下半部分的2/3和1/3，这保证了最佳的平均性能，即在递归之前将列表分成O(N^(2/3))个子列表，每个子列表包含O(N^(1/3))个元素。

- paperclip optimizer

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- templatetypedef · Accepted Answer

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
√256 = 16 的平方根为 16
√16 = 4 的平方根为 4
√4 = 2 的平方根为 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)次。

现在，让我们进行一些数学运算，使其更加严谨。让我们用二的幂来重新表达上面的序列：

√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除以2 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树）数据结构。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 closest pair of points algorithm，该算法试图在一组2D点中找到两个最接近的点。它通过创建一个桶的网格并将点分配到这些桶中来工作。如果在算法的任何时刻发现一个桶中有超过√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)的树层上执行二分查找，因此其某些操作的运行时间为O(log log U)。相关的y-fast trie通过维护每个包含O(log U)个节点的平衡BST来获得它的O(log log U)运行时间，允许在这些树中进行搜索时间为O(log log U)。tango tree和相关的multisplay tree数据结构由于维护包含O(log n)项的树而在其分析中出现了一个 O(log log n) 项。

其他例子

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