python - 字典排序的时间复杂度

Question

我想知道按键排序字典和按值排序字典的时间复杂度是多少。

例如:

for key in sorted(my_dict, key = my_dict.get):
  <some-code>

在上一行中，sorted 的时间复杂度是多少？如果假设使用快速排序，平均 O(NlogN) 和最坏情况下的 O(N*N) 是吗？

按值排序和按键排序的时间复杂度是否不同？因为 ，通过键访问值只需要 O(1) 时间，两者应该相同？

谢谢。

Answer 1

sorted 并不是真正对字典进行排序；它将接收到的可迭代对象收集到列表中，并使用 Timsort algorithm 对列表进行排序. Timsort 绝对不是快速排序的变体，它是一种更接近归并排序的混合算法。根据维基百科，其复杂度在最坏情况下为 O(n log n)，并通过优化来加速常见的偏序数据集。

由于收集字典的键和值都是O(n)，所以两种排序的复杂度是一样的，由排序算法确定为O(n log n)。