多维哈希的空间复杂度
我想存储制表符分隔值的输入，其中 C1、C2、C3 和 C4 表示数据的列，并且有 N 行数据。如果是这样，我可以在哈希中进行查找，以查看 C1、C2、C3、C4 的某些给定值是否存在。有人向我建议，在最坏的情况下，其空间复杂度为 N4。我希望得到帮助来明确解释为什么这不是真的。
I would like to store an input of tab separated values where say C1, C2, C3 and C4 represent the columns of the data and there are N rows of data. If so, I could do lookups in the hash to see if some given values for C1,C2,C3,C4 exist. Someone suggested to me that, in the worst case, the space complexity of this was N4. I would like help formulating a clear explanation as to why that is not true.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
另一个人认为，如果您尝试存储 N × N 点网格，则将存储 N4 个点。
但如果你有 N 个点，那么你只是存储一个哈希值。具有 N 个数据点的哈希通常需要 O(N) 空间。 （从技术上讲，它需要哈希表的大小加上数据的空间，但人们通常动态地将哈希表调整为与数据集大小相同的数量级。）
The other person is thinking that if you try to store an N by N grid of points, there will be N4 points to store.
But if you have N points, then you're just storing a hash. And a hash with N data points typically takes O(N) space. (Technically it takes the size of the hash table plus the space for the data, but people usually dynamically size the hash table to be the same order of magnitude size as the data set.)