nedtrie上的搜索操作的复杂性（逐行搜索结果）

Question

我最近听说过关于nedtries并决定尝试实现它们，但是一些让我困扰的是他们搜索操作的复杂性;我不明白为什么他们应该这么快。

根据我的理解，他们的搜索操作的预期复杂度应该是 O（m/2），其中密钥的大小以位为单位。 如果在传统的二进制树比较它的搜索操作的复杂性， 你： 的log 2（N）> = M/2

让我们的重点是32位长：LOG 2（N）> = 16 < => n> = 65536

因此，从65536个项目开始，所有的项目都应该比二叉树更快。然而，作者声称他们总是比二叉树快，所以无论是我的假设 对他们的复杂性都是错误的，或者在搜索的每一步执行的计算在网上都快得多。

那么，它呢？

Answer 1

如果你有更小的树，你可以使用更小的键！

Answer 2

（注意我是作者的nedtries）。我认为我在页面前面的复杂性解释是合理的？也许不是。

您缺少的关键是它确定复杂度的位之间的差异。差异越大，搜索成本越低，而差异越小，搜索成本越高。

这个作品的实际情况源于现代无序处理器。简单地说，如果你避开主存，你的代码运行速度比依赖主存更快40-80倍。这意味着你可以在从内存中加载单个东西所需的时间内执行50-150个操作。这意味着您可以进行一次扫描并找出我们应该继续查看的节点，而不会比将该节点的缓存线加载到内存中的时间长得多。

这有效地消除了复杂性分析中的逻辑，位扫描和其他一切。他们都可能是O（N^N），并不重要。现在最重要的是，选择下一个要查看的节点是有效的，因此必须加载的节点数量是缩放约束，因此它是从总数中查看的平均节点数量这是其平均复杂度的节点，因为主存缓慢是迄今为止最大的复杂性约束。

这是否有意义？这意味着奇怪的是，如果某些位密集包装在密钥的一端而松散地包装在密钥的另一端，那么密集包装的一端的搜索将非常慢（接近O（log N），其中N是数字的密集元素）比在松散包装的末尾搜索（接近O（1））。

不久之后，我将着手添加利用这种按位尝试功能的新功能，因此您可以说“将此节点添加到松散/密集的空间并返回您选择的密钥”以及各种类型在这个主题上的变化。可悲的是，一如既往，这取决于时间和对时间的要求。

尼尔