是什么会导致算法具有O（log log n）复杂度？
这个较早的问题解决了可能导致算法具有O（log n）复杂度的一些因素。
是什么会导致算法具有时间复杂度O（log log n）？
回答：
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 16也是这种情况。
但是，如果我们在每个级别取平方根，
- √65,536= 256
- √256= 16
- √16= 4
- √4= 2
请注意，仅需四个步骤即可将其降至2。这是为什么呢？好吧，让我们用2的幂重写此序列：
- √65,536=√2 16 =（2 16）1/2 = 2 8 = 256
- √256=√2 8 =（2 8）1/2 = 2 4 = 16
- √16=√2 4 =（2 4）1/2 = 2 2 = 4
- √4=√2 2 =（2 2）1/2 = 2 1 = 2
注意，我们遵循序列2 16 →2 8 →2 4 →2 2 →2 1。在每次迭代中，我们将指数的二分之一减半。这很有趣，因为这与我们已经知道的联系在一起-
您只能在将k降为零之前将其除以O（log k）的一半。
因此，取任意数字n并将其写为n = 2
k。每次取n的平方根，都会使该方程式的指数减半。因此，在k降至1或更低（在这种情况下n降至2或更低）之前只能应用O（log k）个平方根。由于n = 2
k，这意味着k = log 2 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 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 logn是正确的解决方案。诸如Cheriton-Tarjan
MST算法之类的某些算法通过解决复杂的约束优化问题而到达包含O（loglog n）的运行时。
希望这可以帮助！
以上是 是什么会导致算法具有O（log log n）复杂度？ 的全部内容， 来源链接： utcz.com/qa/417978.html
