python - 通过将列表转换为集合然后再转换回列表来对列表进行排序的时间复杂度

Question

我最近观看了Raymond Hettingers talk about python dictionaries (并通过扩展集...)他提到整数会散列到自身，并且将整数添加到字典(或集...)将按顺序插入它们，只要您不删除项目，顺序就会是保留在 python 3.6(可能更高版本？)中。在this question的回答中据说字典保留插入顺序，但对于集合来说，它就像整数根据其值排序一样。

现在:根据time-complexity section of python.org更详细地here据说向集合添加元素的平均时间复杂度是 O(1)。这意味着如果您有一个未排序的整数列表，则应该可以通过简单地执行以下操作来对它们进行排序:

sorted_list = list(set(unsorted_list))

据我测试，情况似乎如此(使用随机序列进行了几千次)。

我现在的问题是:这是否意味着可以在 O(n) 时间内对 python 中的整数进行排序？

对我来说，它是这样的，因为构建集合需要 O(n) ，将集合转换回列表需要 O(n) ，还是我在这里遗漏了一些东西？

Answer 1

不，一般来说不是。您一定已经在特殊情况下尝试过了，例如未排序的输入列表包含从 0 到 n 的所有数字，每个数字一次。

这是一个失败的简单案例:

>>> list(set([8, 1]))
[8, 1]

使用 CPython 3.8.1 32 位完成。