时间戳

首页 > 解决方案 > 哈希表中插入的最坏情况复杂度

algorithm - 哈希表中插入的最坏情况复杂度

问题描述

给定一个负载因子为 2 的外链哈希表，并且哈希函数和键比较需要时间，那么在其中插入 N 个项目的最坏情况复杂度是多少？

我的想法
我们必须插入 N 个项目，并且负载因子是 2，因此插入每个项目要么需要一步或两步，所以复杂度应该是 Theta(N)
我不确定这个参数是否正确

标签： algorithmhashtable

解决方案

如果您谈论最坏的情况，您必须考虑如果必须增加哈希表的容量会发生什么。负载因子 2 意味着哈希表将被重建为具有更高容量的哈希表。新容量将是x * oldcapacity我假设 x 约为 2 的地方。

一个不好的情况是 N=1 并且必须进行完整的重新散列。这导致 O(N + M) 与 M 是表的大小。如果 M >> N，这是最坏的情况。

让我们说桌子是空的。有趣的问题是“我们最多需要重复多少次？” 假设表以容量 2 开始为空。那么第一次插入将导致第一次重新散列。那么容量是4，这样第二次insert就会引起rehashing。所以导致重新散列的元素是 [1,2,4,8,16, ...]。

这意味着我们对表进行了 log(N) 次重新哈希。最难的问题还没有到来。每个元素多久重新散列一次？

  • 第一个元素将被重新散列 log(N) 次。
  • 第二个元素将被重新散列 log(N-1) 次。
  • 第四个元素将被重新定义 log(N-2) 次。
  • 最后一个元素将被重新散列 1 次。

所有重新散列的总和是 O(log(n!)) = O(n*log(n))

推荐阅读