我在分析 Python 的字典插入 运行 时间时出了什么问题？
What am I getting wrong analyzing Python's Dict insert running time?
据我了解 Python 源代码，插入字典的工作方式类似于：
insert(e)
- 令
j 为已分配数组中的元素数，k 为数组的大小。 （初始化时 k 为 8）。
- 如果
j+1 < 2/3k，将e插入hash(e)%k位置（暂且不担心碰撞）
- 否则，将数组大小调整为两倍大小的数组。
k 现在是两倍大，这需要 O(k_prev)
对于 n 插入，有 log(n)-3 调整总时间复杂度 O(log(n)) 但所有在线资源似乎都说我应该将此操作视为 O(1) ？
当他们说 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 的数组复制 6 个元素到 16。我们将 12 个元素复制到大小为 32 的数组。我们将 24 个元素复制到大小为 64 的数组。
[我使用 ^ 表示求幂，而不是异或。]
所以我们最终将总共 6(1 + 2 + 4 + ... 2^n) 个元素复制到一个 2^(n + 3) 的数组中。但是第一个数字小于 6 * 2^(n + 1) 即 1.5 * 2^(n * 3)。因此，无论我们当前的数组大小如何，复制到数组的总量都小于数组大小的 1.5 倍。
重新散列实际上是 O(n) 成本，但考虑到它很少见且相对便宜（散列是预先计算和缓存的，你知道 none 现有元素是相等的，所以一个完整的桶可以假设不相等），这通常没什么大不了的。
所以不，任何给定的操作实际上可能是 O(n)。但很像 list 扩展，它是 amortized O(1) 插入（从技术上讲，平均情况 O(1) 插入；即使没有重新散列的给定插入也可能是 O(n) 如果你设法确保所有被插入的项目散列到相同的散列模底层存储大小，但 Python 最小化内置类型）。
它保持 O(1) 摊销的原因是每个元素的（重新）插入的平均次数仍然受常数乘数的约束，这在大 O 术语中是可以忽略的。您实际上可能对每次插入取 O(2) 或 O(3) 的平均值，但因为 数量 的重新散列 下降 成正比对于重新散列的 size（完成的工作），它真正做的只是意味着您更频繁地进行插入工作，但它并没有增加每个元素的 平均值 随着 dict 增长的成本。
据我了解 Python 源代码，插入字典的工作方式类似于：
insert(e)
- 令
j为已分配数组中的元素数，k为数组的大小。 （初始化时k为8）。 - 如果
j+1 < 2/3k，将e插入hash(e)%k位置（暂且不担心碰撞） - 否则，将数组大小调整为两倍大小的数组。
k现在是两倍大，这需要O(k_prev)
对于 n 插入，有 log(n)-3 调整总时间复杂度 O(log(n)) 但所有在线资源似乎都说我应该将此操作视为 O(1) ？
当他们说 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 的数组复制 6 个元素到 16。我们将 12 个元素复制到大小为 32 的数组。我们将 24 个元素复制到大小为 64 的数组。
[我使用 ^ 表示求幂，而不是异或。]
所以我们最终将总共 6(1 + 2 + 4 + ... 2^n) 个元素复制到一个 2^(n + 3) 的数组中。但是第一个数字小于 6 * 2^(n + 1) 即 1.5 * 2^(n * 3)。因此，无论我们当前的数组大小如何，复制到数组的总量都小于数组大小的 1.5 倍。
重新散列实际上是 O(n) 成本，但考虑到它很少见且相对便宜（散列是预先计算和缓存的，你知道 none 现有元素是相等的，所以一个完整的桶可以假设不相等），这通常没什么大不了的。
所以不，任何给定的操作实际上可能是 O(n)。但很像 list 扩展，它是 amortized O(1) 插入（从技术上讲，平均情况 O(1) 插入；即使没有重新散列的给定插入也可能是 O(n) 如果你设法确保所有被插入的项目散列到相同的散列模底层存储大小，但 Python 最小化内置类型）。
它保持 O(1) 摊销的原因是每个元素的（重新）插入的平均次数仍然受常数乘数的约束，这在大 O 术语中是可以忽略的。您实际上可能对每次插入取 O(2) 或 O(3) 的平均值，但因为 数量 的重新散列 下降 成正比对于重新散列的 size（完成的工作），它真正做的只是意味着您更频繁地进行插入工作，但它并没有增加每个元素的 平均值 随着 dict 增长的成本。