python - 从不同长度的字典中弹出项目时的时间差异

Question

我正在用 Python 设计一个软件，我对从长度非常小的字典中弹出项目和从长度非常大的字典中弹出项目时是否有任何时间差异感到好奇，或者在所有情况下都相同.

Answer 1

timeit您可以使用该模块轻松地为自己回答这个问题。但是字典的整个要点是通过键近乎即时地访问任何所需的元素，所以我不希望这两种情况之间有很大的区别。

Answer 2

查看这篇关于 Python TimeComplexity的文章：

为 dict 对象列出的平均案例时间假定对象的散列函数足够健壮以使冲突不常见。平均情况假设参数中使用的键是从所有键的集合中均匀随机选择的。

请注意，（在实践中）仅处理 str 键的 dicts 有一条快速路径；这不会影响算法的复杂性，但会显着影响常数因素：典型程序完成的速度。

根据这篇文章，对于“获取项目”操作，平均情况是 O(1)，更糟糕的情况是 O(n)。换句话说，最坏的情况是时间随着大小线性增加。有关更多信息，请参阅Wikipedia 上的Big O 表示法。