Python any 和 in 和 for 循环的时间复杂度

Question

以下代码行的时间复杂度(一般/最坏情况)是多少？

s1 = "any-string-of-large-size" 
s2 = "anyother-string-of-larger-size"  
if(any(x in s1 for x in s2)):
    return "YES"
return "NO"

此代码用于检查 s1 和 s2 是否有共同的字母。我还希望有任何其他方法来实现这一目标，这可能会更有效。
我发现使用此类库函数时很难计算时间复杂度。有人可以解释一下如何计算吗

Answer 1

最好和最坏的情况分别是 O(1) 和 O(|s1|*|s2|)，其中 |s1| code> 和 |s2| 表示两个字符串的长度。

事实上，您的代码可以重写为

for c2 in s2:
   for c1 in s1:
      if c1==c2:
          return "YES"
return "NO"

如果你只是想检查两个字符串是否共享一个公共(public)字符，你可以将其写为

if set(s1) & set(s2):
   return "YES"
return "NO"

这将具有相同的最坏情况时间复杂度O(|s1|*|s2|)，但平均情况为O(min(|s1|,|s2|) )。