为什么Python中set(array)比列表sort()排序的实现运行速度更快？

核心性能差异来源 #

两个版本的性能差距并非来自排序算法，而是成员查询操作in的时间复杂度差异，你对set的实现逻辑存在误解：Python的set底层基于哈希表实现，全程不涉及排序操作，和列表的sort()方法用到的Timsort排序算法完全无关。

第一个版本（sort+列表）的时间复杂度计算 #

• 列表sort()排序的时间复杂度为O(n log n)，这部分开销实际上并不大，针对1e5长度的列表仅需十几万次操作
• 致命瓶颈在循环内的if i+k in ar：列表的in查询是顺序遍历匹配，单次查询时间复杂度为O(n)，循环执行n次后，这部分总时间复杂度达到O(n²)
• 当n=1e5时，n²对应100亿次操作，远超过编程题的时间限制，自然会超时

第二个版本（set）的时间复杂度计算 #

• 列表转set的过程是将每个元素哈希后存入散列表，平均时间复杂度为O(n)
• set的in查询是通过哈希函数直接计算元素存储位置，无需遍历，单次查询平均时间复杂度为O(1)，循环执行n次后总时间复杂度仅为O(n)
• 整体总时间复杂度为O(n)，1e5长度仅需十万次左右操作，完全符合时间要求

补充说明 #

如果你想继续用排序的思路解题，可以在排序后改用双指针法实现匹配，总时间复杂度为O(n log n)，同样可以通过测试用例，效率也远高于你最初的列表查询版本。

内容的提问来源于stack exchange，提问作者Rifat Bhuiyan