遍历SortedDict元素的时间复杂度：我的O(nlogn)理解是否正确？

先看你给出的代码：

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)

你的理解不正确，这段遍历代码的时间复杂度是O(n)，理由如下：

• SortedDict（sortedcontainers库中的实现）底层采用分段数组结合二分查找的结构，但针对遍历操作做了专门优化。它内部维护着有序的元素序列，调用items()返回的迭代器可以直接按顺序遍历底层的有序存储，不需要每次都执行O(logn)的查找操作。
• 你混淆了随机访问和顺序遍历的区别：通过键随机获取单个元素（比如d['a']）确实是O(logn)的时间复杂度，但顺序遍历是直接沿着有序序列逐个读取，每个元素的访问开销是均摊O(1)，整体遍历的时间复杂度就是O(n)。
• 实际上，SortedDict的设计目标之一就是在保证增删改查操作O(logn)性能的同时，让遍历操作保持和普通字典一致的O(n)效率，这也是它的核心优势之一。

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