我最近听说了 nedtries 并决定尝试实现它们，但我对它们的搜索操作的复杂性感到困扰；我无法忍受他们为什么要这么快。
据我了解，他们的搜索操作的预期复杂度应该是 O(m/2)，其中 m 是密钥的大小（以位为单位）。如果将其与传统二叉树中搜索操作的复杂性进行比较，您会得到：log2(n) >= m/2
让我们的密钥长度为 32 位：log2(n) >= 16 <=> n >= 65536
所以 nedtries 应该比从 65536 个项目开始的二叉树更快。然而，作者声称它们总是比二叉树快，所以要么我对它们复杂性的假设是错误的，要么在搜索的每一步执行的计算在 nedtrie 中要快得多。
那么，它呢？
（注意我是 nedtries 的作者）。我认为我在 nedtries 页面前面对复杂性的解释有道理吗？也许不是。
您缺少的关键是决定复杂性的是位之间的差异。差异越大，搜索成本越低，而差异越小，搜索成本越高。
这个工作的事实源于现代的乱序处理器。简单来说，如果您避免使用主内存，您的代码运行速度比依赖主内存快 40-80 倍。这意味着您可以在从内存加载单个事物所需的时间内执行 50-150 个操作。这意味着您可以进行一点扫描并找出我们接下来应该查看的节点，其时间不会超过将该节点的缓存线加载到内存中的时间。
这有效地消除了复杂性分析中的逻辑、位扫描和其他所有内容。它们都可能是 O(N^N) 并且没关系。现在重要的是下一个要查看的节点的选择实际上是免费的，因此必须加载以进行检查的节点数是缩放约束，因此它是查看的节点总数中的平均节点数节点，这是它的平均复杂度，因为主存的缓慢是迄今为止最大的复杂度限制。
这有意义吗？这意味着奇怪，例如如果某些位在密钥的一端密集打包，但在密钥的另一端松散打包，则在密集打包端的搜索将非常慢（接近 O(log N)，其中 N 是数字密集元素）而不是在松散包装端（接近 O(1)）中搜索。
很快有一天，我将开始添加利用按位尝试这一特性的新函数，因此您可以说“将此节点添加到松散/密集的空间并返回您选择的密钥”以及各种变体主题。可悲的是，一如既往，它归结为时间和对时间的要求。
尼尔
如果你有更小的树，你可以使用更小的键！