如何计算递归解决方案的时间复杂度？

Question

我正在求解 word break problem 并且我已经使用动态规划对其进行了优化，并且该解决方案也有效。但是我无法 calculate/figure 计算出这种方法的时间复杂度。

代码：

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);
    }
};

谁能帮我逐步理解上述算法的时间复杂度？

谢谢

Answer 1

对于每个 i ∈ [0..n)（n 是 s 的长度），您的递归函数只执行一次完整的内循环（因为第二次结果将缓存在 DP).

此时你可能会说整个算法是 O(n²)，但事实并非如此，这里有一个转折。

您标记为 O(n) 的内部循环实际上不是 O(n)，而是 O(n²)，因为您正在搜索 next（s 的子字符串） unordered_dict。每个这样的搜索需要 O( next.length ) 时间，并且由于 next 的长度范围是 0..length(s)，dict 搜索是 O(n)，因此内部循环是 O(n²)。

鉴于以上所有，整个算法是 O(n³)：O(n) 来自递归并乘以来自内循环的 O(n²)。

或者，准确地说，O(n³ + k)，其中 k 是 wordDict 中所有字符串的累积大小（因为您是从它们构建集合）。

P.S。为了将复杂度降低 O(n) 倍，您可以使用 Trie 而不是 unordered_set 来存储来自 wordDict 的单词。这样你的算法就是 O(n² + k).

如何计算递归解决方案的时间复杂度？

How to calculate the time complexity of a recursive solution?

recursion

time-complexity