python - 比较列表交集的算法

Question

我正在尝试设计一种算法来查找已排序数组和不同数组之间的共同元素。我正在使用以下两种方法之一。就运行时和时间复杂度而言，哪一个更好？

方法一:

# O(n^2) ?
common = []

def intersect(array1,array2):
    dict1 = {}
    for item in array1:
        dict1.update({item:0})
    for k,v in dict1.iteritems():
        if k in array2:
             common.append(k)          
    return common

print intersect(array1=[1,2,3,5], array2 = [5,6,7,8,9])

方法二:

# probably O(n^2)
    common = []

def intersect(array1,array2):
    for item1 in array1:
        for item2 in array2:
            if (item1==item2): 
                common.append(item1)
    return common

print intersect(array1=[1,2,3,5], array2 = [5,6,7,8,9])

Answer 1

设 array1 有 M 个元素，array2 有 N 个元素。第一种方法的时间复杂度 O(M lg N)。第二种方法的时间复杂度为 O(M*N)。因此，从时间复杂度的角度来看，第一个更好。但是请注意，第一种方法的空间复杂度为 O(M)，而第二种方法则没有。

顺便说一句，可能有一个O(max(M, N))算法。