用n个元素初始化散列表的运行时间是什么？

Question

是O（n）还是O（n logn）？我有n个需要在哈希表中设置的元素，什么是最坏情况和平均运行时间？

Answer 1

最坏的情况是无限的。您需要计算哈希代码，并且可能需要比较元素，并且时间不限。

假设计算哈希和比较元素是恒定时间，插入最坏的情况是O（n^2）。实际上，最糟糕的情况会非常罕见，假设中途体面有功能，那么可以节省您的是什么。体面实施的平均时间是O（n）。