排序容器的时间复杂度
Time complexity for a sorted container
我正在使用 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)？在 sorteddict 的情况下是 log(n) 还是 O(n) 因为我需要访问最后一个元素？
sortedcontainers SortedDict 维护密钥顺序，在幕后，在 sortedcontainers.SortedList 中。所以你问的操作真的是SortedList.__getitem__()。来自 the docs:
__getitem__(index)[source]
Lookup value at index in sorted list.
sl.__getitem__(index) <==> sl[index]
Supports slicing.
Runtime complexity: O(log(n)) – approximate.
现在是对数时间。
我正在使用 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)？在 sorteddict 的情况下是 log(n) 还是 O(n) 因为我需要访问最后一个元素？
sortedcontainers SortedDict 维护密钥顺序，在幕后，在 sortedcontainers.SortedList 中。所以你问的操作真的是SortedList.__getitem__()。来自 the docs:
__getitem__(index)[source] Lookup value at index in sorted list.
sl.__getitem__(index) <==> sl[index]
Supports slicing.
Runtime complexity: O(log(n)) – approximate.
现在是对数时间。