两种Python重复元素检测方案时间复杂度均为O(N)，为何实际耗时差异大？

解决方案1： #

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        return len(nums) != len(set(nums))

解决方案2： #

class Solution(object):
    def containsDuplicate(self, nums):
        hset = set()
        for idx in nums:
            if idx in hset:
                return True
            else:
                hset.add(idx)

出现耗时差异的核心原因如下：

• 提前终止的巨大优势
  方案2的逻辑是遇到第一个重复元素就立刻返回结果，不需要处理数组剩余的元素。比如如果数组前几个元素就存在重复，方案2只需要循环几次就能结束，而方案1必须把整个数组完整遍历一遍，将所有元素插入集合后再比较长度，这种场景下两者的操作量天差地别，耗时自然拉开差距。

• 时间复杂度的局限性
  O(N)是渐近时间复杂度，它只描述数据量趋近于无穷大时的时间增长趋势，不代表实际运行的绝对耗时。两个同复杂度的算法，在常数项、实际操作量上可能有很大区别——方案1的操作量固定为N（不管有没有重复都要处理所有元素），而方案2的操作量在最坏情况（无重复）下是N，最好情况是2（前两个元素重复），平均操作量远小于方案1。

• 底层实现的细节差异
  虽然Python的set()构造是C语言实现的，单步操作比Python层面的for循环更快，但这个优势只有在处理全部元素时才能体现。一旦方案2可以提前终止，哪怕单步循环慢，总操作量的减少会完全抵消这个劣势，甚至反超。而如果是完全没有重复的测试用例，方案1反而可能更快，但这种场景下两者的耗时差异不会像有重复时那么显著。

内容的提问来源于stack exchange，提问作者HIMANSHU WAGH