algorithm - 有没有需要 O(1) 时间的算法？

Question

我正在寻找O(1)两者都需要时间的算法search and insertion。

有没有可用的算法？是否可以？

score 1 · Accepted Answer

假设哈希是完美的，并且计算哈希的时间是 O(1)，理论上您可以进行 O(1) 的插入和搜索哈希映射。

score -3 · Accepted Answer

这不可能。读取您将插入的键将是最好的 O(log n)，因为键必须以二进制表示。因此，每次将大小加倍时，都需要向密钥添加一个额外的二进制数字，因此它不会是 O(1)。更不用说实际插入值了。

除非我们在谈论量子计算？

2 回答 2