字典排序的时间复杂性

Question

我想知道按键排序字典和按值排序字典的时间复杂性是什么？

例如：

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

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

按值排序和按键排序的时间复杂性是否不同？既然，通过键访问值只需要O(1)时间，那么两者应该是相同的吗？

谢谢。

Answer 1

sorted并不真正对字典进行排序；它将接收到的可迭代性收集到列表中，并使用Tim排序算法对列表进行排序。Timsort显然不是快速排序的变体，它是一种更接近合并排序的混合算法。根据wikipedia的说法，在最坏的情况下，它的复杂性是O(n log n)，通过优化来加快常见的部分有序数据集的速度。

由于收集到的切分键和值都是O( n)，这两种排序的复杂性是相同的，由排序算法确定为O(n log )。