Python字典列表构造时间复杂度及末尾键值对弹出O(1)实现问询

1. 字典转列表的时间复杂度 #

list(my_dict.keys())的时间复杂度是O(n)——因为要遍历字典里所有n个键，逐个复制到新列表中。这直接导致你当前的代码整体时间复杂度是O(n)，完全达不到你想要的O(1)要求。

2. 实现O(1)弹出最后一个键值对的方案 #

从Python 3.7开始，字典正式保留插入顺序，以下两种方法能实现平均O(1)的弹出操作：

方法一：直接用dict.popitem() #

Python 3.7+的popitem()默认弹出最后插入的键值对，平均时间复杂度就是O(1)：

last_key, last_val = my_dict.popitem()

注：Python 3.6及更早版本中popitem()是随机弹出的，不保证顺序，但3.7+已把插入顺序纳入语言规范。

方法二：用collections.OrderedDict（兼容旧版本） #

如果需要兼容Python 3.6及更早版本，OrderedDict的popitem(last=True)方法可以精准弹出最后插入的键值对，平均时间复杂度同样是O(1)：

from collections import OrderedDict

my_odict = OrderedDict()
# 插入键值对...
last_key, last_val = my_odict.popitem(last=True)

3. 你当前方案的效率问题 #

list(my_dict.keys())[-1]先把所有键转成列表（O(n)），再取最后一个元素（O(1)），最后执行pop（O(1)），整体耗时由O(n)主导，字典越大效率越低。

内容的提问来源于stack exchange，提问作者Rayan Zakaria Hassici