为什么将.values（）和.keys（）确切地视为O（1）？

Question

无法找到足够坚实的理由来解释为什么将字典函数（如.values（）和.keys（））以大O表示法视为O（1）。（不确定.items（）是否也视为O（1））

Answer 1

我不精通python，但是我发现了这一点：

字典视图对象

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

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

这意味着dict.keys()诸如此类不会返回新对象，而只是可以循环访问字典的瘦包装器。所以得到这种观点是O(1)。遍历元素并非如此。

Answer 2

您发现.keys()和.values()（和.items()）为O（1）的引用可能会强调性能，因为它与Python 2相反，在Python 2中，这些函数返回了列表，并且需要O（N）时间才能将引用复制到所有相关对象在字典之外。

迭代在Python 3中由这些方法返回的视图对象仍将花费O（N）时间，因为无法避免访问每个项目，因为这是整个迭代的重点。在keys和items意见献的O（1）会员资格测试（例如(somekey, somevalue) in somedict.items()），这是很多不是搜索列表中的一个项目更有效。