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

概述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

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)吗？

@H_403_14@解决方法 发布的代码实际上是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).

总结

以上是内存溢出为你收集整理的python – 这个函数的Big O表示法是什么？全部内容，希望文章能够帮你解决python – 这个函数的Big O表示法是什么？所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。