是什么会导致算法具有O（log log n）复杂度？

大佬教程收集整理的这篇文章主要介绍了是什么会导致算法具有O（log log n）复杂度？，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。

如何解决是什么会导致算法具有O（log log n）复杂度？？

开发过程中遇到是什么会导致算法具有O（log log n）复杂度？的问题如何解决？下面主要结合日常开发的经验，给出你关于是什么会导致算法具有O（log 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？如果我们这样做，我们得到

@H_675_14@

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也是这种情况。

但是，如果我们在每个级别取平方根，

@H_675_14@

√65,536= 256

√256= 16

√16= 4

√4= 2

请注意，仅需四个步骤即可将其降至2。这是为什么呢？好吧，让我们用2的幂重写此序列：

@H_675_14@

√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 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）复杂度？全部内容，希望文章能够帮你解决是什么会导致算法具有O（log log n）复杂度？所遇到的程序开发问题。

如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。