我有一个哈希表，其中包含 1000 个元素和 100 个存储桶，每个存储桶最多包含 100 个条目。假设一个存储桶有 100 个条目(即该存储桶的列表中有 100 个项目)。现在，如果我寻找的项目是存储桶列表中的第 100 个项目，则以大 O 表示法表示的时间复杂度是多少。 O(100) 还是 O(n)？还是其他什么？
最佳答案
big-O 表示法的要点是，您不要“假设一个存储桶有 100 个条目”，而是让其条目数为 n，并得到一个以 表示的表达式>n.
对于列表中的 n 个条目，时间复杂度将为 O(n)，忽略您使用的任何哈希函数。
请注意，这是最坏的情况(最后一项)，平均搜索时间为 O(1)。
关于c++ - 链式哈希表的时间复杂度是多少，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/24242242/