这个较早的问题解决了可能导致算法具有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？如果我们这样做，我们得到
此过程需要16个步骤，并且65,536 = 2 16也是这种情况。
但是，如果我们在每个级别取平方根，
请注意，仅需四个步骤即可将其降至2。这是为什么呢？好吧，让我们用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）的运行时。
希望这可以帮助！
