time-complexity - HashSet的时间复杂度

Question

我正在和朋友讨论使用 mod 函数作为 Hashing 函数的 Hashset 设计。这种实现的时间复杂度似乎是 O(N/K) ，其中 N 是存储在集合中的总项目，k 是桶的总数。该时间复杂度假设所有项目都分布在所有桶中，桶的平均大小为 N/K。

我很困惑，因为我相信时间复杂度应该是 O(N)。由于时间复杂度是最坏情况下的性能。这里最坏的情况可能是所有 N 个项目都进入同一个桶，我们正在寻找的值可能在桶的末尾。请在这里帮助我。

标签： time-complexity

Answer 1

你是对的，最坏的情况是所有物品都进入一个桶。物品均匀分布是最好的情况。也就是说，如果 k 保持不变，则 O(N/k) 与 O(N) 相同，因为可以忽略常数。无论如何，我不希望 k 成为查找输入的一部分。如果 k 可以变化，那么它是不同的，但最坏的情况仍然是 O(N)。