对数与双对数时间复杂性

Question

在现实世界中，使用$ Mathcal {o}（ log（ log（n））$而不是$ MATHCAL {O}（ log（n））$算法时，使用$ mathcal {o}（ log（ log（n））$时，是否会有具体的好处？

当一种用法而不是更常规的二进制搜索树实现的情况下，就是这种情况。但是，例如，如果我们采用$ n <10^6 $，那么在最好的情况下，双对数算法的表现优于（大约）$ 5 $的对数。而且总的来说，实施更加棘手和复杂。

鉴于我个人更喜欢BST而不是Veb-Trees，您怎么看？

一个人可以轻松证明：

$ qquad displaystyle forall n <10^6。

Answer 1

不要忘记，$ log n $仍然比$ log（ log n）$快（在$ log（n）$中成倍增长（在$ log（n）$中）！

实际上，如果您查看$ log（n）$和$ log（ log（n））$的商，那么看到：

^[资源]

但是，您仍然获得了最高$ 100000 $的尺寸五到六的因子。请注意，实践中较大尺寸并不少见 惊人的呢这可能会在午餐后或明天获得结果之间有所不同。请注意，一部分加速可能会被树木实施的较高常数所消失。您将必须用$ c cdot log（n）$和$ d cdot log（ log（n））$绘制（或分析）$ c cdot log（n）$（ log（n））$，$ c，d $是实际的运行时常数，以获取真实图片。

此外，戴夫（Dave）提到的重要内容很重要：如果该操作逐渐加速执行，例如，经常线性地执行，恒定的加速会变成线性加速，即您可以减少整个算法的领先常数！正如我在上面说的那样，真是太棒了。只需查看如果您运行操作$ n $ times会发生什么：

^[资源]

现在，如果这不值得麻烦，我不知道什么。

Answer 2

可以想象，复杂性的差异确实并不重要，而且实际运行时间更为重要。但是，如果该算法是另一种算法的核心，那么这种差异可能很重要。

从纯粹的理论目的来看，差异当然确实很重要，尤其是如果算法是另一个算法的一部分。它可能将较大的算法放在不同的复杂性类别中。

Answer 3

实际上，我自己曾经对范·埃姆·波阿斯树进行了基准测试。我将其与AA树，一个hashmap和一些数组进行了比较。

测试执行 size 在间隔中插入随机数 [0, bound], ， 然后 size 然后搜索 size 删除，然后又 size 搜索。删除也在随机数上完成，因此您首先必须弄清楚它们是否完全处于结构中。

这是结果（size=2000000, bound= 10000000）几秒钟：

AATreeLookup - O(n log n)
Inserting... 3.3652452
Searching... 5.2280724
Deleting...  7.3457427
Searching... 9.1462039
HashLookup - O(n) expected
Inserting... 0.3369505
Searching... 0.6223035
Deleting...  0.9062163
Searching... 1.1718223
VanEmdeBoasTree - O(n log log n)
Inserting... 0.7007531
Searching... 1.1775800
Deleting...  1.7257065
Searching... 2.2147703
ArrayLookup - O(n)
Inserting... 0.0681897
Searching... 0.1720300
Deleting...  0.2387776
Searching... 0.3413800

如您所见，Van Emde-Boas树的速度约为哈希地图的两倍，十倍慢，是位阵列的慢，是二进制搜索树的速度的5倍。

当然，以上需要免责声明：测试是人造的，您可以改进代码或使用其他语言与编译器使用其他语言，该编译器的输出速度更快，依此类推。

该免责声明是我们在算法设计中使用渐近分析的原因的核心：由于您不知道常数是什么，并且由于常数可以根据环境因素而改变，因此我们能做的最好的是渐近分析。

现在，在$ log n $ vers $ log log n $的情况下：在上面的示例中，我的van emde-boas树能够包含$ 2^{32} $元素。 $ log 2^{32} = 32 $，$ log 32 = 5 $，这是一个因素6改进，在实践中相当多。此外，Van Emde-Boas树具有良好的恒定因素（这与实践中的不变因素有关，因为差异很小），因为它们不需要平衡自己。