Python字典.values()/.items()/.keys()的时间与辅助空间复杂度咨询

1. .values()、.items()和.keys()的时间与空间复杂度 #

• 创建视图时：时间复杂度为O(1)，辅助空间复杂度为O(1)。这些方法不会复制字典的任何数据，仅返回一个绑定到原字典的轻量视图对象，仅存储指向原字典的引用及少量内部状态，内存占用与字典大小N无关。
• 遍历视图时：时间复杂度为O(N)，因为需要逐个访问原字典的所有元素，但遍历过程不会额外分配O(N)级别的空间（若显式转换为列表，如list(d.values())，则会占用O(N)空间）。

2. 函数foo的辅助空间复杂度 #

对于这段代码：

def foo(d):
    bar = d.values()

辅助空间复杂度为O(1)。d.values()返回的视图对象本身仅占用固定内存（如原字典引用、状态标识），不会随字典条目数增长。原字典d属于函数输入参数，其空间不计入辅助空间范畴。

3. 函数foo的时间复杂度 #

该函数的时间复杂度为O(1)。创建视图对象仅需完成简单的初始化操作，无需遍历字典元素，耗时与字典大小无关。

视图对象的运作核心 #

视图是动态绑定的引用层，不存储原字典的任何键值数据，直接关联原字典的内部结构。当原字典修改（增删改条目）时，视图会实时同步变化——每次访问视图元素，都是直接从原字典读取最新数据，而非依赖缓存的副本。

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