什么会导致算法具有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.在我们降到1之前,我们有多少次将其除以2？如果我们这样做,我们就会得到

• 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.为什么会这样？好吧,让我们用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 ^{1进行操作}.在每次迭代中,我们将二次幂的指数削减.这很有趣,因为这可以连接到我们已经知道的东西 - 你只能将数字k除以它在降至零之前的一半O(log k)次.

所以取任意数n并将其写为n = 2 ^k.每次取n的平方根时,将该等式中的指数减半.因此,在k降至1或更低之前,只能应用O(log k)平方根(在这种情况下,n降至2或更低).由于n = ^2k,这意味着k = log ₂ n,因此所取的平方根的数量是O(log k)= O(log log n).因此,如果存在通过将问题重复地减少到原始问题大小的平方根大小的子问题而工作的算法,则该算法将在O(log log n)步骤之后终止.

一个真实的例子是van Emde Boas树(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点集合中的两个最接近的点.它的工作原理是创建一个桶网格并将这些点分配到这些桶中.如果在算法中的任何点处发现其中具有多于√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)中运行.在探戈树和相关multisplay树的数据结构,结束了一个O(日志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)的运行时.

希望这可以帮助!