插入哈希表的最坏情况复杂度为
O(n)
。
但是,当创建新的哈希表并插入
n
元素时,据我了解,这会导致 n
插入到不断增长的哈希表中。因此,O(1) + O(2) + O(3) + ... + O(n) = O((n^2+n)/2)
。因此,创建具有 n
元素的哈希表的最差运行时复杂度将是二次的。这是正确的吗?
但是,插入的平均和摊销运行时复杂度为
O(1)
,因此使用 n
元素创建哈希图的平均和摊销运行时复杂度也将是 O(1)
?
如果您在每次插入时调整大小 1(或任何其他常数),那么您不会得到
O(1)
,而是像您的分析所示的 O(n)
。
相反,我们会根据哈希表中当前元素数量的某个因子来调整大小,例如,每当哈希表被填满时,您就将哈希表的大小加倍(实际上,我们会使用一些负载因子,而不是等到已满)。
因此,例如,如果哈希表中的项目数为
n
并且刚刚调整了大小,则最大可能的项目数为 2n
。
因此,现在要进行下一次调整大小,您需要至少执行 n
插入,然后调整大小也是 O(n)
,因此摊销是 O(1)
。