初始化具有n个元素的哈希表的运行时是什么

Question

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

Answer 1

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

假设计算散列和比较元素是恒定时间，对于插入，最坏的情况是O（n^2）。拯救你的是，假设一个半吊子有作用，最坏的情况会非常罕见。良好实施的平均时间为O（n）。