这个自上而下的动态编程代码的时间复杂度是多少？

Question

我不能像下面的例子那样分析自顶向下动态规划方法的时间复杂性。你能帮帮我吗？

问题：给定一个字符串s和一个字符串字典wordDict，如果s可以被分割成一个或多个字典单词的空格分隔序列，则返回true。注意，词典中的同一个词可能在切分中被重复使用多次。

输入:s=“catsandog”,worddict=[“cats”,“dog”,“sand”,“cat”]
输出:false

输入:s=“leetcode”,worddict=[“leet”,“code”]
输出:true

bool match(string &s,int l,int n,string &wordDict) {
    int i = 0;
    while(l < n && i < wordDict.size()) {
        if (s[l] != wordDict[i])
            return false;
        l++;
        i++;
    }
    return i == wordDict.size();
}
bool wordBreakUtil(string &s, int l, int n, vector<string>& wordDict, map<int,bool> &m) {
    if (l==n)
        return true;
    if (m.find(l) != m.end()) {
        return m[l];
    }
    int i;
    for(i=0;i<wordDict.size();i++) {
        if (match(s,l,n,wordDict[i])) {
            if (wordBreakUtil(s,l+wordDict[i].size(),n,wordDict,m))
                return true;
        }
    }
    m[l] = false;
    return false;
}
bool wordBreak(string s, vector<string>& wordDict) {
    int n = s.size();
    map<int,bool> m;
    return wordBreakUtil(s,0,n,wordDict,m);
}

Answer 1

通过将递归调用中完成的计算工作与其他工作分开，可以找到memoised DP算法的最坏情况界限。具体来说，我们需要确定：

1. 使用不同的输入（参数值）调用递归函数的最大可能次数--这是函数必须“完成它的工作”而不是快速返回已经计算好的答案的最大可能次数。
2. 对递归函数的每次调用中所做的最大工作量，不包括对其本身的递归调用。

然后，我们可以将（1）的答案乘以（2）的答案，得到一个上界。（这个界限可能不是很紧，因为问题中可能存在结构，这意味着实际上避免了递归函数调用的渐近重要数量，或者每个调用中所做的工作量远小于这些调用的渐近重要部分中可能的最大值，或者两者兼而有之--但在实践中，它通常是紧的。）

递归函数wordbreakutil()用6个不同的参数调用，但实际上只有其中一个参数L随每次调用而变化。因为我们在M中记录结果，所以当我们处理以前从未见过的L值时，我们可以保证只将结果传递到函数的主体(for循环）：这意味着（1）的答案是WordBreakutil()可以调用的不同的L值的最大数量，即n+1（值0、1、2、...、n)。渐近地，这是O(n)。

假设字典中有k单词。在WordBreakutil()中，它所做的最大工作量（不包括对自身的递归调用）为O(kn)。这是因为它循环k次，每次都调用match()，match()在其循环中最多执行n步骤。（您可以将match()的复杂性描述为L，其中L是字典中任何字符串的最大长度，也可以将其更精确地描述为min(n,L)，但是添加L参数会使表达式更加复杂，而不会提供太多信息。）对于M.find(l)调用，还有一个log k加法项，但这是由O(kn)项主导的，因此在WordBreakutil()中完成的非递归工作仍然是O(kn)。

这意味着总的执行时间以O(kn^2)为界。