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

Question

无法找到足够可靠的理由来解释为什么.values()和.keys()等字典函数在大 O 表示法中被认为是O(1) 。（不确定.items()是否也被认为是 O(1) ）

Answer 1

.keys()您发现和.values()(and ) 为 O(1)的引用很可能.items()强调了性能，因为它与 Python 2 形成对比，在 Python 2 中，这些函数返回列表并且需要 O(N) 时间来复制对所有相关对象的引用出字典。

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

Answer 2

我不精通python，但我发现了这个：

字典视图对象

和 返回的对象dict.keys()是视图对象。它们提供字典条目的动态视图，这意味着当字典更改时，视图会反映这些更改。dict.values()dict.items()

可以迭代字典视图以产生它们各自的数据，[...]

这意味着 that dict.keys()and such 不会返回一个新对象，而只是一个可以遍历字典的薄包装器。所以得到这个观点是O(1)。迭代元素不是。