algorithm - 求哈希函数的摊销复杂度

Question

当我遇到这个问题时，我正在准备期末考试。
对于 1a，我认为它的 O(1) 用于摊销复杂性，因为它执行足够稀疏的 x mod N 并且线性探测以防它失败但是我不确定如何准确地陈述或证明这一点。

对于 1b，它会散列到同一个地方，因此每次插入时它都会线性探测更多，但我也不确定如何从中派生运行时。

Answer 1

[已编辑，我最初的分析是针对开放哈希而不是开放寻址] 对于 1a) h(x) = x mod N, n < N，因此哈希值为 0, 1, ..., n - 2, 0。除了最后一个插入之外，所有插入都将是无碰撞的。最后一次插入将使用线性探针。第一个探测到存储桶 0，但它被占用并且密钥不同。下一个探测位于插槽 1，结果相同，直到它到达 (n - 1) 处的第一个空桶。因此，总共需要 (n - 1) 次额外操作，总共 (2n - 1)。每次插入的摊销成本为 (2n - 1)/n。

对于 1b)，哈希表退化为链表。插入的大小是线性的，有 n 次插入，因此总共有 (n + 1) * n / 2 次操作。即每次插入 (n + 1)/2。

Answer 2

1a，除了最后一次之外，根本不会发生碰撞（N会与每个值发生碰撞，即N会先与0发生碰撞，然后将值增加1，它将与1发生碰撞，依此类推），总成本将是 1+1+...+1+n = (n-1 次)+n=2n-1，摊销成本将是 (2n-1)/n，它是 O(1)大 O 符号。

1b，第 i 次插入将有 (i-1) 次冲突，加上插入操作，第 i 次操作的成本将为 i。所以总成本是1+2+...+n-2+n-1+n=(n+1)*n/2，你插入了n次，摊销成本就是(n+1) /2。