以下代碼行的時間復(fù)雜度（一般/最壞情況）是多少？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 是否有共同的字母。我還希望有任何其他方法來實(shí)現(xiàn)這一目標(biāo)，這可能會更有效。我發(fā)現(xiàn)使用此類庫函數(shù)時很難計算時間復(fù)雜度。有人還可以解釋一下如何計算嗎
2 回答
精慕HU
TA貢獻(xiàn)1845條經(jīng)驗 獲得超8個贊
最好和最壞的情況分別是O(1)和O(|s1|*|s2|)，其中|s1|和|s2|表示兩個字符串的長度。
事實(shí)上，你的代碼可以重寫為
for c2 in s2:
for c1 in s1:
if c1==c2:
return "YES"
return "NO"
如果您只想檢查兩個字符串是否共享一個公共字符，您可以將其寫為
if set(s1) & set(s2):
return "YES"
return "NO"
這將具有相同的最壞情況時間復(fù)雜度O(|s1|*|s2|)，但平均情況是O(min(|s1|,|s2|)。
慕慕森
TA貢獻(xiàn)1856條經(jīng)驗 獲得超17個贊
(in)關(guān)鍵字的時間復(fù)雜度一般為O(N)。所以 s2 中的 x 是直接的 O(N)。由此得出總體復(fù)雜度為 O(N^2)。
添加回答
舉報
0/150
提交
取消