blow 函数的时间复杂度是多少？
what is the time complexity of blow functions?
哪个函数的时间复杂度较低？为什么？
我想比较 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)
TL;DR
在现实世界中，这取决于您使用的数据。小尺度方法之间的差异可以忽略不计，而大尺度方法之间的差异很大。
大 O 表示法
话虽这么说，如果您正在寻找类似理论 big-O notation 的东西，那么我们必须看看 list() 和 set() 以及 zip() 实施。一个非常基本的经验法则是将 n 范围内的每个循环视为 n 的顺序，然后进行加法、乘法等
例如，函数 compare_with_for() 是 O(n^2) 因为它迭代 list1 (n) 并且每个元素迭代 list2 (n) 所以 n*n=O(n^2).
编辑：其他big-O近似由用户在评论中回答。像 Dor Meiri 这样的用户，他们的努力值得赞扬。我不会把他们的答案改写成我的，所有的功劳都是他们的。
Python
中的执行时间
为了安排代码的执行时间，您可以按照用户 Dor Meiri[= 的建议使用 timeit 或 time.perf_counter 48=].
以下是使用后者的方法：
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：
按照 Dor Meiri.
的建议将 time.time() 更改为 time.perf_counter()
编辑 2：
改进格式。
compare_with_set 平均为 O(n)，最坏情况为 O(n^2)，因为集合创建为 O(n)，集合迭代为 O(n)，集合搜索为 O(1 ) 在平均情况下，在最坏情况下为 O(n)
compare_with_zip 是 O(n) 因为迭代是 O(n)，追加和比较是 O(1)
compare_with_for 是 O(n^2) 因为迭代和搜索是 O(n)
备注：compare_with_zip与其他结果不一样
哪个函数的时间复杂度较低？为什么？ 我想比较 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)
TL;DR
在现实世界中，这取决于您使用的数据。小尺度方法之间的差异可以忽略不计，而大尺度方法之间的差异很大。
大 O 表示法
话虽这么说，如果您正在寻找类似理论 big-O notation 的东西，那么我们必须看看 list() 和 set() 以及 zip() 实施。一个非常基本的经验法则是将 n 范围内的每个循环视为 n 的顺序，然后进行加法、乘法等
例如，函数 compare_with_for() 是 O(n^2) 因为它迭代 list1 (n) 并且每个元素迭代 list2 (n) 所以 n*n=O(n^2).
编辑：其他big-O近似由用户在评论中回答。像 Dor Meiri 这样的用户，他们的努力值得赞扬。我不会把他们的答案改写成我的，所有的功劳都是他们的。
Python
中的执行时间为了安排代码的执行时间，您可以按照用户 Dor Meiri[= 的建议使用 timeit 或 time.perf_counter 48=].
以下是使用后者的方法：
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： 按照 Dor Meiri.
的建议将time.time() 更改为 time.perf_counter()
编辑 2： 改进格式。
compare_with_set 平均为 O(n)，最坏情况为 O(n^2)，因为集合创建为 O(n)，集合迭代为 O(n)，集合搜索为 O(1 ) 在平均情况下，在最坏情况下为 O(n) compare_with_zip 是 O(n) 因为迭代是 O(n)，追加和比较是 O(1) compare_with_for 是 O(n^2) 因为迭代和搜索是 O(n)
备注：compare_with_zip与其他结果不一样