英文:
What is the runtime complexity of this function considering that "in" is like a nested loop looking at lists as input?
问题
def disjoint(lst1, lst2):
res = True
for x in lst1:
if x in lst2:
res = False
return res
所以我认为这个函数的运行时间复杂度是O(n^2)，因为在Python中的“in”操作也具有O(n)的运行时间复杂度，其中n是列表的大小，但是我的老师不知何故将其标记为错误。顺便说一下，该函数应该根据两个列表是否不相交返回一个布尔值。(不要介意函数效率低下，它是给我们的，后续问题是实现一个更有效率的解决方案)
英文:
python code:
def disjoint(lst1,lst2):
res = True
for x in lst1:
if x in lst2:
res = False
return res
So I thought this function has a runtime complexity of O(n^2) since "in" in Python also has a runtime complexity of O(n) with n = size of the list but my teacher somehow marked it as a mistake. Btw the function should return a boolean based on wether two lists are disjoint or not. (Dont mind that the function is inefficient it was given to us like that the follow up question was to implement a more efficient solution)
答案1
得分: 1
I'll assume the sizes of lst1 and lst2 are n and m respectively
你可以假设 lst1 和 lst2 的大小分别为 n 和 m
You have an outer loop that runs n times, and another one inside that runs m times. So you would get a time complexity of O(n*m).
你有一个外部循环运行了 n 次，里面又有一个循环运行了 m 次。因此，时间复杂度为 O(n*m)。
However if lst1 and lst2 are not lists, the time complexity of the in operator might be different.
但是，如果 lst1 和 lst2 不是列表，那么 in 运算符的时间复杂度可能会不同。
For a set or dict the worst-case time complexity of in is O(n) and average-case of O(1), so for those you would get an average time complexity of O(n+m), if n=m then its average O(n).
对于集合或字典，in 运算符的最坏情况时间复杂度为 O(n)，平均情况为 O(1)，因此对于这些数据结构，你会得到平均时间复杂度为 O(n+m)，如果 n=m，那么平均时间复杂度为 O(n)。
英文:
I'll assume the sizes of lst1 and lst2 are n and m respectively
You have an outer loop that runs n times, and another one inside that runs m times. So you would get a time complexity of O(n*m).<br>
However if lst1 and lst2 are not lists, the time complexity of the inoperator might be different.<br>
For a set or dict the worst-case time complexity of in is O(n) and average-case of O(1), so for those you would get an average time complexity of O(n+m), if n=m then its average O(n).
答案2
得分: 0
给定你的情况和代码，你的列表中可能包含唯一元素。在这种情况下，使用集合可能是一个更好的选项。
def disjoint(lst1, lst2):
lst1, lst2 = set(lst1), set(lst2)
return len(lst1.intersection(lst2)) == 0
print(disjoint([1, 2, 3, 4, 5, 6, 7], [1, 2]))
print(disjoint([1, 2, 3, 4, 5, 6, 7], [8, 9]))
输出：
False
True
如果列表的长度分别为 m 和 n，你的代码需要 O(mn) 的时间，而集合的交集操作只需要 O(n) 的时间，其中 n 是较小列表的长度。
英文:
Given your case and code, you might be having unique elements in the lists. In that case, sets might be a better option.
def disjoint(lst1,lst2):
lst1, lst2 = set(lst1), set(lst2)
return len(lst1.intersection(lst2)) == 0
print(disjoint([1, 2, 3, 4, 5, 6, 7], [1, 2]))
print(disjoint([1, 2, 3, 4, 5, 6, 7], [8, 9]))
Output:
False
True
If the length of lists were m and n respectively, your code was taking O(mn) time, whereas the set intersection will take O(n) where n is the length of the smaller list.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论