python - 为什么 .values() 和 .keys() 被认为是 O(1)？

Question

无法找到足够可靠的推理来解释为什么像 .values() 和 .keys() 这样的字典函数被认为是 O(1) 在大 O 符号中。 (不确定 .items() 是否也被认为是 O(1) )

Answer 1

您找到的对 .keys() 和 .values()(以及 .items())的引用很可能是O(1) 强调性能，因为它与 Python 2 形成对比，在 Python 2 中，那些函数返回列表并需要 O(N) 时间将对所有相关对象的引用复制到字典之外。

在 Python 3 中对这些方法返回的 View 对象进行迭代仍将花费 O(N) 时间，因为无法避免访问每个项目，因为这是迭代的全部要点。 keys 和 items View 确实提供 O(1) 成员资格测试(例如 somedict.items() 中的 (somekey, somevalue))，这比搜索列表中的项目更有效。