0
是O(n)还是O(n logn)?我有n个需要在哈希表中设置的元素,什么是最坏情况和平均运行时间?用n个元素初始化散列表的运行时间是什么?
是O(n)还是O(n logn)?我有n个需要在哈希表中设置的元素,什么是最坏情况和平均运行时间?用n个元素初始化散列表的运行时间是什么?
最坏的情况是无限的。您需要计算哈希代码,并且可能需要比较元素,并且时间不限。
假设计算哈希和比较元素是恒定时间,插入最坏的情况是O(n^2)。实际上,最糟糕的情况会非常罕见,假设中途体面有功能,那么可以节省您的是什么。体面实施的平均时间是O(n)。