c++ - 确定代码的运行时间

Question

我今天写了下面的 dp 代码，它工作得很好，因为它在提交时得到了一些分数(here is the problem)。但是我无法确定我的代码的运行时间。我觉得它是 O(n^2 * log D) 但我无法证明。

class Solution {
public:
    unordered_map<string, bool> m;
    bool wordBreak(string s, unordered_set<string>& wordDict) {
        int n = s.length();
        string t = "";
        for(int i=0;i<n;i++){
            t += s.at(i);
            //cout << t << endl;
            if(wordDict.find(t) != wordDict.end()){
                m[t] = true;
                string x = "";
                for(int j=i+1;j<n;j++){
                    x += s.at(j);
                }
                if(x == ""){
                    return true;
                }
                if(m.find(x) != m.end()){
                    if(m[x] == true){
                        return true;
                    }else{
                        continue;
                    }
                }else{
                    if(wordBreak(x, wordDict)){
                        m[x] = true;
                        return true;
                    }else{
                        //cout << x << endl;
                        m[x] = false;
                        continue;
                    }
                }
            }else{
                //m[t] = false;
            }
        }
        return false;
    }
};

Answer 1

它似乎有 O(n*n) 复杂度。您使用内存，算法的每一步都会在 m 中产生至少 1 个新值。任何字符串中都有n*n/2个子串，所以最坏情况下你会找到整个字符串有n*n/2个段落的解。

PS:考虑 unordered_map 使用 O(1)。

编辑:

在您的情况下，考虑 unordered_map 使用 O(n) 可能更合适。 m.find 需要为其参数计算哈希值，即字符串。如果您存储索引而不是字符串本身，它可能会工作得更快。