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