我有两段用 python 编写的代码。
对于A代码,时间复杂度为O(n^2),因为迭代器内部存在remove。
并且由于return中存在join方法,所以该行的时间复杂度为O(n),所以我认为整个代码的时间复杂度为O(n^2)。
B代码中使用的collections.Counter,时间复杂度为O(n),我认为是O(n^2),因为它在一行中与join方法一起使用。
但是这两个代码似乎有不同的表现。
如果忽略常数时间,为什么两种代码会有性能差异?
一个
def solution(participant, completion):
for i in completion: participant.remove(i)
return "".join(participant)
B
import collections
def solution(participant, completion):
return "".join(collections.Counter(participant) - collections.Counter(completion))
请您参考如下方法:
第一个解决方案的复杂度为 O(m * n + k),其中 m、n 是两个列表的大小和 k=m-n.
第二种解决方案具有复杂的计算 O(m + n + k)。
此外,您还必须考虑实现方面,Counter 是用 C/C++ 编写的,'-' 操作是用 C/C++ 编写的,您的代码代替m上的循环在python中,remove()在n上的操作在C/C++中
