python – 这个函数的Big O表示法是什么？

发布时间：2020-12-20 11:07:43 所属栏目：Python 来源：网络整理

导读：def scramble(s1,s2): arrs1 = list(s1) arrs2 = list(s2) if all(True if arrs2.count(item) = arrs1.count(item) else False for item in arrs2): return True else: return False 我正在尝试创建一个函数,可以测试字符串字符(str1)的一部分是否可以重新排

def scramble(s1,s2):
    arrs1 = list(s1)
    arrs2 = list(s2)

    if all(True if arrs2.count(item) <= arrs1.count(item) else False for 
item in arrs2):
        return True
    else:
        return False

我正在尝试创建一个函数,可以测试字符串字符(str1)的一部分是否可以重新排列以匹配另一个字符串(str2).

这不是O(n)吗？

解决方法

发布的代码实际上是O(n ^ 2)：

all(True if arrs2.count(item) <= arrs1.count(item) else False for item in arrs2)

所有这些都需要对输入进行单次传递,从而产生O(n)的时间复杂度.但是,在每次传递时,必须获取项目在arrs2和arrs1中出现的次数. count是O(n)的复杂性,因为列表对象也必须迭代以找到所需值的每次出现. count方法被调用两次,但是,它的近似于O(n)作为平均时间复杂度.因此,完整表达式是O(n)* O(n)=>为O(n ^ 2).

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!