字符串連接檢查算法的運行時間

Question

我寫了一個算法來檢查一個字符串是否是數組中任意數量字符串的連接（同時能夠多次使用一個字符串）。我無法準確計算算法的運行時間。

我檢查數組中的每個單詞的字符串，當我發現一個字是從索引0開始的原始字符串的子字符串時，我檢查數組中每個單詞的剩餘子字符串。所以我認爲這是一個O（n^n），除非我失去了一些東西。

def check_concat(str,substr,words) 
    if substr == "" 
    return false 
    end 

    words.each do |word| 
    if word == substr && str != substr 
     return true 
    end 
    if substr.index(word) == 0 
     if check_concat(str,substr[word.length..-1],words) 
     return true 
     end 
    end 
    end 
    return false 
end 

Answer 1

讓我們假設你的主字符串包含m words，並在陣列中n words要搜索有。在最糟糕的情況下，您需要檢查主字符串中的每個單詞與數組中的每個單詞，即mn時間。因此該功能的時間複雜度爲O(mn)。

例如，主字符串是"Hello Hello Hello Hello Hello"。要檢查的數組包含以下詞'Hai', 'Fine', 'Hello'。然後該功能將需要總共15次比較。