algorithm - 插入和搜索时哈希表的时间复杂度

Question

看着Wikipedia对于哈希表，它说插入和搜索是 O(1)。但我担心的是，我的老师告诉我只有查找是 O(1) 并且散列是 O(s)，其中 s 字符串的长度。插入和搜索不应该是 O(s) 吗？它说哈希(s) + 查找(s)= O(哈希(s) + 查找(s>))= O(s)。

谁能解释一下用大 O 表示法为哈希表编写时间复杂度的正确方法是什么，为什么？如果假设它是完美散列并且没有发生冲突。

Answer 1

哈希表不仅仅用于字符串。插入和查找的 O(1) 复杂度一般适用于哈希表，并且只计算已知操作。

散列和比较计算为 O(1)，因为必须始终为这些做某事，即使您只是存储整数，但我们不知道那是什么。

如果您对某些数据类型(如字符串)使用哈希表，这会成倍增加这些操作的成本，那么它也会成倍增加复杂性。

在衡量使用哈希表的具体算法的复杂性时，考虑这一点实际上非常重要。例如，该站点上的许多基于字符串的算法都基于输入字符串的长度受某个常数限制的假设而被赋予了复杂性。值得庆幸的是，情况通常如此。