我正在解決斷字問題，我已經使用動態編程對其進行了優化，并且該解決方案也有效。但我無法計算/弄清楚這種方法的時間復雜度。
代碼：
class Solution {
public:
int util(string &s, int i, unordered_set<string> &dict, vector<int> &DP) {
if(i >= s.size()) {
return 1;
}
if(DP[i] != -1) {
return DP[i];
}
string next = "";
for(int itr = i; itr < s.size(); itr ) { // O(N)
next = s[itr];
if(dict.find(next) != dict.end() and util(s, itr 1, dict, DP)) { // ?
return DP[i] = 1;
}
}
return DP[i] = 0;
}
bool wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> dict(wordDict.begin(), wordDict.end());
vector<int> DP(s.size() 1, -1);
return util(s, 0, dict, DP);
}
};
誰能幫我一步一步地理解上述演算法的時間復雜度？
謝謝
uj5u.com熱心網友回復：
對于每個i ∈ [0..n)( nis length of s)，您的遞回函式只執行一次完整的內部回圈（因為第二次結果將被快取在 中DP）。
此時你可能會說整個演算法是 O(n2)，但事實并非如此，有一個轉折。
您標記為O（n），內環實際上不是為O（n），但O（N2），因為你要搜索next（子串s的）unordered_dict。每個這樣的搜索都需要O( next.length )時間，并且由于長度next從 開始0..length(s)，dict 搜索是 O(n)，因此內部回圈是 O(n2)。
鑒于以上所有，整個演算法是 O(n3)：來自遞回的 O(n) 乘以來自內回圈的 O(n2)。
或者，準確地說，是 O(n3 k)，其中k是 中所有字串的累積大小wordDict（因為您正在從它們構造集合）。
PS 為了通過 O(n) 的因子降低復雜性，您可以使用Trie而不是unordered_set從wordDict. 這樣你的演算法就是 O(n2 k)。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/359909.html