分析Python Dict插入操作的时间复杂度时我的推导哪里出错了？

你的核心问题出在两个地方：一是总扩容时间的计算错误，二是混淆了最坏时间复杂度和均摊时间复杂度的定义。

• 首先纠正总扩容时间的计算逻辑：
  你提到的扩容次数是log(n)-3次是对的，但不能直接得出总扩容时间是O(logn)。每次扩容的时间复杂度是O(k_prev)，也就是和扩容前的数组大小成正比。我们可以把所有扩容的成本列出来：
  初始大小8，第一次扩容成本8（扩容到16），第二次扩容成本16（扩容到32），第三次32，以此类推，直到最后一次扩容到刚好能容纳n个元素的大小（最大不超过2n）。这是一个首项为8、公比为2的等比数列，总和是2^(m+1)-8，最终结果小于4n，也就是说总扩容时间是O(n)，不是O(logn)。
• 再讲均摊时间复杂度的计算逻辑：
  行业内说dict插入是O(1)，默认指的是均摊时间复杂度，不是单次操作的最坏时间复杂度。我们可以把每次扩容的O(k)成本，平摊到触发这次扩容的所有前置插入操作上：只有当插入元素数量达到当前数组容量的2/3时才会触发扩容，也就是说这次O(k)的成本可以平摊到2k/3次插入操作上，平摊到每次操作的成本就是O(1)。剩下的不需要触发扩容的插入操作本身就是O(1)，所以整体算下来所有插入操作的均摊时间复杂度就是常数级。
• 补充说明：单次插入的最坏时间复杂度确实是O(n)（刚好触发扩容的那次插入），但这种情况出现的概率极低，且随着数据量增大，平摊后的成本始终保持常数，所以我们日常描述哈希表操作复杂度的时候，都会直接说O(1)。

内容的提问来源于stack exchange，提问作者Wren