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|和|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|)。

Answer 2

(in)关键字的时间复杂度一般为O(N)。所以 s2 中的 x 是直接的 O(N)。由此得出总体复杂度为 O(N^2)。