哈希表创建运行时复杂性

Question

插入哈希表的最坏情况复杂度为

O(n)

。

但是，当创建新的哈希表并插入

n

元素时，据我了解，这会导致

n

插入到不断增长的哈希表中。因此，

O(1) + O(2) + O(3) + ... + O(n) = O((n^2+n)/2)

。因此，创建具有

n

元素的哈希表的最差运行时复杂度将是二次的。这是正确的吗？

但是，插入的平均和摊销运行时复杂度为

O(1)

，因此使用

n

元素创建哈希图的平均和摊销运行时复杂度也将是

O(1)

？

Answer 1

如果您在每次插入时调整大小 1（或任何其他常数），那么您不会得到

O(1)

，而是像您的分析所示的

O(n)

。

相反，我们会根据哈希表中当前元素数量的某个因子来调整大小，例如，每当哈希表被填满时，您就将哈希表的大小加倍（实际上，我们会使用一些负载因子，而不是等到已满）。

因此，例如，如果哈希表中的项目数为

n

并且刚刚调整了大小，则最大可能的项目数为

2n

。 因此，现在要进行下一次调整大小，您需要至少执行

n

插入，然后调整大小也是

O(n)

，因此摊销是

O(1)

。