any和in-and-for循环的Python时间复杂性

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

（in）关键字的时间复杂度一般为O（N）。所以s2中的x是向前的O（N）。总的复杂度是O（N^2）

Answer 2

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

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

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

如果您只想检查这两个字符串是否共享一个公共字符，您可以将其写入

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

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