排序字典的时间复杂度

Question

7

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

例如：

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

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

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

谢谢。

- Novice

Python使用Timsort算法进行排序。https://dev59.com/z3I_5IYBdhLWcg3wHvQ5 - Gennady Kandaurov

它们并不不同，两者都是具有N个成员的列表。 - ᴀʀᴍᴀɴ

1

你不能对字典进行排序，只能对从字典中返回的序列进行排序。如果你直接尝试迭代它，你会得到一个仅包含键而不包含值的序列。 - Mark Ransom

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- user4815162342 · Accepted Answer

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

由于收集字典键和值的复杂度都是O(n)，因此两种排序的复杂度相同，由排序算法决定，为O(n log n)。