分析给定Python代码的时间复杂度（大O表示法）

结论先行 #

该函数的平均时间复杂度为O(N)，既不是O(N^3)，也不需要表述为O(N+N+N)——大O标记法会自动忽略同量级下的常数系数、线性项累加，多个平级的线性步骤合并后仍为线性复杂度。

完整参考代码（修正原代码缩进问题） #

def finder(arr1,arr2):
    count={}
    # 第一个循环：统计arr1元素出现次数
    for x in arr1:
        if x in count.keys():
            count[x]+=1
        else:
            count[x]=1
    # 第二个循环：统计arr2元素出现次数
    for x in arr2:
        if x in count.keys():
            count[x]-=1
        else:
            count[x]=1
    # 第三个循环：找计数不为0的元素
    for key,num in count.items():
        if num != 0:
            return key
    return ('equal arrays')

逐段复杂度推导 #

首先统一前提：设两个数组的总元素规模为N（该函数的典型使用场景是两数组长度差为固定常数，比如arr2比arr1少1个元素，因此arr1、arr2的长度都和N呈线性关系，量级均为O(N)）。

• 初始化空字典count是常数级操作，耗时固定为O(1)，不影响整体复杂度。
• 第一个遍历arr1的循环：循环总执行次数等于arr1的长度，属于O(N)次迭代。注意Python3中count.keys()返回的是字典键的视图对象，x in count.keys()本质是走哈希表查找，平均时间复杂度为O(1)，循环内的计数增减、判断逻辑全是常数级操作，因此这部分整体平均复杂度为O(N)。
• 第二个遍历arr2的循环：逻辑和第一个循环完全一致，循环总执行次数等于arr2的长度，内部操作全是平均O(1)的常数操作，这部分平均复杂度同样为O(N)。
• 第三个遍历字典键值对的循环：字典中存储的键的总数最多为arr1、arr2中所有不同元素的数量，上限不会超过两数组长度之和，量级仍为O(N)。且循环遇到第一个计数不为0的键就直接返回结果，最坏情况才会遍历完所有键，因此这部分的平均、最坏复杂度均为O(N)。

常见误区说明 #

• 为什么不是O(N^{3)：整个代码的三个循环是完全平级的，不存在任何循环嵌套结构，不会出现幂次级的复杂度增长。只有三层嵌套循环每层都遍历N个元素时，才会出现O(N}3)的复杂度，该代码不满足这个条件。
• 为什么不写O(N+N+N)：大O标记法关注的是输入规模增大时，算法耗时的增长趋势，常数倍的线性操作累加不会改变「耗时随输入规模线性增长」的本质，因此三个线性步骤合并后统一记为O(N)即可，不需要拆分累加。
• 极端情况补充：如果出现极端哈希冲突，字典的in操作可能退化为O(N)，但这是概率极低的特殊场景，算法分析中一般默认采用平均时间复杂度作为结论。

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