迭代 SortedDict 中的项目的时间复杂度？

Question

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次。我的理解正确吗？

Answer 1

SortedDict.items() calls SortedItemsView(self), the constructor of which is inherited from collections.abc.MappingView via collections.abc.ItemsView, and ItemsView has the following special method:

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

So you're right that it is doing a lookup at each step. Here, self._mapping is a SortedDict. However, since SortedDict is a subclass of dict that does not override __getitem__, it uses the standard dict.__getitem__, which is O(1) on average, better than O(log n).

Also note that the for key in self._mapping: above calls sortedDict.__iter__, which calls SortedList.__iter__, which calls iterools.chain.from_iterable, which runs in linear time.