c - 具有低内存要求的渐近快速关联数组

Question

好的，尝试已经有一段时间了。一个典型的实现应该为您提供独立于数据集大小 n 的 O(m) 查找、插入和删除操作，其中 m 是消息长度。然而，在最坏的情况下，同样的实现每个输入字节占用 256 个字。

其他数据结构，特别是散列，为您提供预期的 O(m) 查找、插入和删除，一些实现甚至提供恒定时间查找。然而，在最坏的情况下，例程要么不会停止，要么会花费 O(nm) 的时间。

问题是，是否有一种数据结构可以提供 O(m) 的查找、插入和删除时间，同时保持与散列或搜索树相当的内存占用？

也许可以说我只对时间和空间方面的最坏情况行为感兴趣。

Answer 1

您尝试过 Patricia-(别名 critbit- 或 Radix-)吗？我认为他们解决了最坏情况下的空间问题。