打击函数的时间复杂度是多少？

Question

哪个函数的时间复杂度较低？为什么？我想比较 python 中的两个列表，但我不知道哪个函数比其他函数更快。

def compare_with_set(list1, list2):
    return list(set(list1) & set(list2))


def compare_with_zip(list1, list2):
    return [i for i, j in zip(list1, list2) if i == j]


def compare_with_for(list1, list2):
    list3 = []
    for item in list1:
        if item in list2:
            list3.append(item)
    return list3


a = [1, 2, 3, 4, 5]
b = [9, 8, 7, 6, 5]

compare_with_set(a, b)
compare_with_zip(a, b)
compare_with_for(a, b)

Answer 1

TL; 博士

在现实世界中，这取决于您使用的数据。小规模的方法之间的差异可以忽略不计，而大规模的方法之间的差异却很大。

大 O 符号

话虽这么说，如果你正在寻找类似的理论大O符号，那么我们就来看看如何list()与set()和zip()实施。一个非常基本的经验法则是将范围内的每个循环视为n有序n，然后进行加法、乘法等
。例如，该函数compare_with_for()的复杂度为 O(n^2)，因为它迭代 list1 (n) 并且对于每个元素遍历 list2 (n) 所以 n*n=O(n^2)。

编辑：用户在评论中回答了其他大 O 近似值。像Dor Meiri这样的用户，他们的努力值得称赞。我不会把他们的答案改写成我的，所有的功劳都是他们的。

Python 中的执行时间

并且为了计时您的代码的执行，您可以简单地使用timeit或time.perf_counter 按照用户Dor Meiri 的建议来执行。

以下是使用后者的方法：

import time

def compare_with_set(list1, list2):
    return list(set(list1) & set(list2))


def compare_with_zip(list1, list2):
    return [i for i, j in zip(list1, list2) if i == j]


def compare_with_for(list1, list2):
    list3 = []
    for item in list1:
        if item in list2:
            list3.append(item)
    return list3


a = [1, 2, 3, 4, 5]
b = [9, 8, 7, 6, 5]

start = time.perf_counter()
compare_with_set(a, b)
end = = time.perf_counter()
duration_compare_with_set = end - start

start = time.perf_counter()
compare_with_zip(a, b)
end = = time.perf_counter()
duration_compare_with_zip = end - start

start = time.perf_counter()
compare_with_for(a, b)
end = = time.perf_counter()
duration_compare_with_for = end - start

编辑1：更改time.time()对time.perf_counter()所建议多尔美日。

编辑 2：改进格式。