Python3中list(dict.keys())的时间复杂度？为何性能逊于OrderedDict.popitem(0)？

时间复杂度 #

list(dict.keys()) 的时间复杂度是 O(n)，其中n代表字典中键值对的总数。因为要把字典里所有的键遍历一遍，再逐个添加到新列表中，这个过程需要线性时间。

关于dict.keys()的误区 #

你提到dict.keys()返回生成器，这个说法不准确——Python3里它返回的是dict_keys视图对象。这个对象是动态的（字典内容变化时视图会同步更新），属于可迭代对象，但并非生成器，遍历它的时间复杂度同样是O(n)。

为什么比OrderedDict.popitem(0)耗时高 #

• OrderedDict.popitem(0)（等价于popitem(last=False)）的时间复杂度是O(1)，因为OrderedDict内部靠双向链表维护键的插入顺序，删除链表头部元素是常数时间操作，不需要遍历整个结构。
• 而list(dict.keys())需要遍历所有n个键并构建新列表，当字典规模较大时，O(n)的操作自然比O(1)的操作耗时多得多。

补充说明：Python3.7及以后的普通字典也会保留插入顺序，但普通字典没有popitem(0)的用法，它的popitem()只能删除最后插入的键（O(1)）；如果要模拟popitem(0)的效果，普通字典得先取第一个键再执行pop，这两步加起来是O(n)，同样比OrderedDict的对应操作慢。

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