代码之家 › 专栏 › 技术社区 › noobie2023

在SortedDict中迭代项目的时间复杂性?

sortedcontainers sorteddictionary python

2

noobie2023 · 技术社区 · 2 年前

from sortedcontainers import SortedDict

d = SortedDict(b=20, d=30, c=10, e=50, a=40)

# What is the time complexity of the following code?
for k, v in d.items():
    print(k, v)

我认为时间的复杂性应该是 nlog(n) 因为从经过排序的字典中获取条目需要花费 log(n) ,即使我们在这个字典上迭代,我们基本上还是执行 get 操作n次。我的理解正确吗?

3 回复 | 直到 2 年前

1

6

Dennis 2 年前

SortedDict.items() 电话 SortedItemsView(self) ,其构造函数为 inherited 从…起 collections.abc.MappingView 通过 collections.abc.ItemsView 和 ItemsView 具有以下特殊方法:

def __iter__(self):
    for key in self._mapping:
        yield (key, self._mapping[key])

所以你是对的,它在每一步都进行查找。在这里 self._mapping 是 SortedDict 。然而,由于 SortedDict is a subclass of dict 不会覆盖 __getitem__ ,它使用标准 dict.__getitem__ ,平均为O(1),好于O(logn)。

还要注意的是 for key in self._mapping: 以上电话 sortedDict.__iter__ ,它调用 SortedList.__iter__ ,它调用 iterools.chain.from_iterable ,以线性时间运行。

2

1

Nick ODell 2 年前

如果我能理解 the code 正确地说,您可以在O(n)中迭代SortedDict的项。

在内部,它使用SortedList,它可以在O(n)时间内迭代所有元素。(SortedList实现为列表列表,它使用 itertools.chain_iterable() 将其转化为单个发电机。)一旦它确定了要访问的正确项,它就可以像普通dict一样在哈希表中查找它

当任何基于比较的排序算法都必须花费最少的O(n-logn)时,这怎么可能呢?当插入到SortedDict中时,可能需要O(logn),因为这就是SortedList takes for insertion. 因此,插入n个项目需要O(n-logn),但对它们进行迭代只需要O(n)。