假设我有一组整数，范围从0到INT64MAX，但是我完全了解该集合，因此可以生成一个完美的哈希。
如果我想将这些哈希值用作数组索引，则需要模量要存储在其中的数组的大小。
这带来了一个问题，我想为我的哈希找到一个非冲突集，该哈希集映射到整数，从而需要最小的数组大小并且我仍然没有冲突。
这个NP完成了吗？它“感觉” NP完成。
有一些算法可以在线性时间内构造出完美的哈希值（甚至是最小的完美哈希值）。例如，请参阅CMPH文档，其中列出了其中的几个。
线性时间意味着确定性多项式问题，因此该问题位于P。P包含在其中NP，但问题当然不比其中最棘手的问题难NP，因此也不存在NP-hard。
NP-complete被定义为是两个 NP和NP-hard。因此，它不是NP完全的。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句