分析Python的Dict insert运行时间有什么错?

事实上,重播 O(n) 成本,但考虑到它很少见,而且相对便宜(散列是预先计算和缓存的,并且您知道现有元素都不相等,所以可以假设一个完整的桶不相等),这通常不是什么大问题。

所以不,任何给定的操作实际上可能是 O(n) .但很像 list 扩张,这是 摊销 O(1) O(1) 插入;即使没有重新灰化,也可以进行给定的插入 O(n) 如果您设法确保插入的所有项都以相同的哈希值模化基础存储大小,但Python会将内置类型的哈希值最小化)。

它仍然存在的原因 O(1) 摊销是指每个元素(重新)插入的平均数量仍受一个常数乘数的约束,该乘数在大O术语中是可忽略的。你可能是在平均 O(2) 或 O(3) 每次插入,但因为 数字 再烧一次就好了 向下 与 大小 (完成的工作)在重新灰烬中,它真正做的只是意味着你正在更频繁地进行插入工作,但这并没有增加 每个元素的平均值 以成本为基础 dict 生长。

当他们说 O(1) ,意思是“摊余成本”。有些手术可能更昂贵,但手术的平均成本仍然很低 O(1) .

我最初的答案如下。我意识到我的证明可以大大简化。

假设当前数组大小为 P = 2^n .一些元素 k 已从上一个数组复制到此数组中。每次复制时,我们复制的元素数量是上一次复制时的两倍。所以移动的元素总数是 k + k/2 + k/4 + ... 这比 2k 这比 2P .

如果我们表演过 N 操作时,数组的大小小于 2N ,我们的表现还不到 4N 副本。因此,副本数量为 O(N) .QED

请注意,我从未在证明中使用过2/3。我们唯一需要的是,每个副本的大小是前一个副本的两倍,并且数组大小与操作数成正比。

这是我最初的答案。

让我们假设在数组已满3/4时复制。这个想法还是一样的,但我们可以用整数。我们从大小为8到16的数组中复制6个元素。我们将12个元素复制到大小为32的数组中。我们将24个元素复制到大小为64的数组中。

[我在用 ^ 指指数,而非排他性或

所以我们最终复制了 6(1 + 2 + 4 + ... 2^n) 元素组成一个数组 2^(n + 3) .但第一个数字小于 6 * 2^(n + 1) 这就是 1.5 * 2^(n * 3) 。因此,无论我们当前使用的是什么大小的数组,到达该数组的复制总量都不到该数组大小的1.5倍。