.values()、.items()、.keys() 的时间和辅助空间复杂度

Question

我最近开始关注 Python 字典的复杂性。然而，当我开始更深入地思考数据结构时，我遇到了几个问题——我正在努力寻找明确的答案：

.values()

、

.items()

和

.keys()

的时间和辅助空间复杂度是多少？我的印象是，由于它们是视图对象，因此它们既不需要额外的空间也不需要额外的时间来检索。通过这种方式，它们几乎就像预先设置的（但动态的）属性。

假设我们有下面的函数

foo

，它需要一个输入字典

d

：

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

虽然该函数的空间复杂度为

O(N)

，其中

N

是字典中的条目数，但该函数的辅助空间复杂度是多少？换句话说，

d.values()

是否会消耗额外的空间？如果是这样，这个函数的辅助空间将是

O(N)

。如果没有，辅助空间就是

O(1)

。

同样，这个函数的时间复杂度是否为

O(N)

（其中

N

是字典中的条目数），还是需要

O(1)

时间运行？

本质上，我试图理解视图对象的机制。谢谢！

Answer 1

它们都需要 O(1) 的时间和空间。它们只是返回一个内部引用字典的小视图对象，因此当您对视图对象执行某些操作时，视图对象实际上会使用字典来执行此操作。