Skip to main content
 首页 » 编程设计

python之比较Python API的时间复杂度

2024年11月01日13lovecherry

我有两段用 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++中