排序容器的时间复杂度

Question

我正在使用 Python 的 SortedDict 容器来解决一个问题，并且想知道获取最高键的时间复杂度是多少：

from sortedcontainers import SortedDict
treeMap = SortedDict()
treeMap[1] = [4]
treeMap[1].append(6)
treeMap[3] = [9]
print(treeMap.keys()[-1]) # get the highest key in the sorted dictionary, should be 3

我知道 SortedDict 中的大多数操作都是 O(log(n)) 但我对 treeMap.keys()[-1] 特别感到困惑。对于普通字典，d.keys()在python3中是O(1)..d.keys()[-1]也是O(1)吗？是 log(n) （在 Sorteddict 的情况下）还是 O(n) （因为我需要访问最后一个元素）？

Answer 1

在幕后sortedcontainers SortedDict，在sortedcontainers.SortedList. 所以你所询问的操作确实是SortedList.__getitem__(). 来自文档：

\n

\n

__getitem__(index)[source]\n在排序列表中的索引处查找值。

\n

sl.__getitem__(索引) <==> sl[索引]

\n

支持切片。

\n

运行时复杂度：近似 O(log(n)) \xe2\x80\x93。

\n

\n

现在是记录时间。

\n