以下Python代码的大O（Big O）时间复杂度是多少？

sample_list = [0, 1, 2, 3, 4, 5, 5, 6]                                          
check_list = []                                                                 
for i in sample_list:                                                           
  if i not in check_list:                                                       
    check_list.append(i)                                                        
  else:
    print(i,end='')

时间复杂度分析 #

你原先判断的*O(n)*不准确，这段代码的最坏时间复杂度为O(n²)，推导逻辑如下：

• 外层for循环遍历sample_list的所有元素，固定执行n次，n为sample_list的元素总数
• 循环内的i not in check_list是核心耗时操作：Python的列表属于线性存储结构，没有索引加速元素存在性判断，每次执行该语句都需要从头遍历check_list的所有元素，单次操作的时间复杂度和check_list当前的长度k正相关，为O(k)
• 最坏场景是sample_list中所有元素完全不重复：每次循环check_list的长度都会增加1，k的取值依次为0、1、2……n-1，所有存在性判断的总耗时为 0+1+2+……+(n-1) = n(n-1)/2，时间复杂度量级为O(n²)
• 只有极少数极端场景（比如所有元素都和第一个元素重复）下，check_list的长度始终为1，单次存在性判断耗时为O(1)，总时间复杂度才会达到O(n)

优化提示：如果要实现O(n)复杂度的找重复逻辑，只需要把check_list改为集合（set）类型即可，集合的元素存在性判断是哈希表实现，单次操作时间复杂度为O(1)，总复杂度就可以降到O(n)

内容的提问来源于stack exchange，提问作者cs-student