以下代碼行的時間復雜度（一般/最壞情況）是多少？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 是否有共同的字母。我還希望有任何其他方法來實現這一目標，這可能會更有效。我發現使用此類庫函數時很難計算時間復雜度。有人還可以解釋一下如何計算嗎
2 回答
精慕HU
TA貢獻1845條經驗 獲得超8個贊
最好和最壞的情況分別是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|)。
添加回答
舉報
0/150
提交
取消